Page 113 - vol1

Gráfok színezési problémái

A gráfelméletben gráfok színezésének nevezzük, amikor színeket (vagy
számokat) rendelünk egy gráf csúcsaihoz, esetleg éleihez. A csúcsszínezés a
kiindulópontja a színezéseknek, tulajdonképpen valamennyi színezést erre
vezetnek vissza és ily módon tanulmányozzák. Hogy milyen céllal végzik ezt?
Nézzük csak az alábbi térkép részletet.

1
1

3 3
4 4

2 2

A térképnek 4 tartománya van, ezek mindegyike egy-egy színnel van kifestve,
legyenek ezek 1, 2, 3, 4. Tekintsünk mind a négy színű tartományban egy-egy
pontot. Ezeket összekötve egy gráfot kapunk. A gráf csúcsai legyenek
ugyanolyan színűek, mint a tartományok ahonnan valók, vagyis 1, 2, 3, 4.
Belátható, hogy a következő két kijelentés egymással egyenértékű:

(1) A négy tartomány mindegyikét kiszínezzük egy-egy színnel úgy, hogy az
egymással érintkező tartományok különböző színűek legyenek.
(2) A gráf négy csúcsát úgy színezzük ki, hogy egy él két végpontján levő
csúcsok nem lehetnek azonos színűek.

A leírt műveletet a gráf színezésének nevezzük. Az első gráfszínezési
eredmények síkbarajzolható gráfokkal voltak kapcsolatosak, a legfontosabb
feladat térképek színezése volt. Amíg Anglia megyéit próbálták meg színekkel
ellátni, Francis Guthrie megfogalmazta a négyszín-sejtést, miszerint 4 szín
elegendő a különböző tartományok megfestéséhez, ha szomszédos
tartományok különböző színeket kapnak. Guthrie testvére továbbította ezt a
kérdést a matematikatanára, Augustus de Morgan felé, aki szintén megosztotta
a sejtést William Hamiltonnal. Arthur Cayley 1879-ben vetette fel a problémát a
London Mathematical Society egy találkozóján. Még ebben az évben Alfred
Kempe nyilvánosságra hozta bizonyítását, és egy évtizeden át helyesnek ítélték.
1890-ben Heawood belátta, hogy Kempe bizonyítása hibás volt. A következő
évszázadban rengeteg ötlet merült fel, hogy sikerüljön ezt a számot 4-re

113