GRÁFOK NÉGYZETMENTES SZÍNEZÉSE
Szerző: Varjú Péter, IV. évfolyam
Témavezető: Dr. Barát János egyetemi adjunktus
Intézmény: Szegedi Tudományegyetem, Természettudományi Kar, Matematikai Intézet

1906-ban Axel Thue norvég matematikus konstruált egy olyan, az 1, 2, 3 számokból álló a0,a1,a2,… végtelen sorozatot, amelyben nem ismétlődik meg kétszer közvetlenül egymásután ugyanaz a blokk, azaz nincsenek olyan l és k egészek, hogy al=al+k, al+1=al+k+1,… al+k-1=al+2k-1. Az ilyen tulajdonságú sorozatokat négyzetmentesnek nevezzük. Ez az eredmény sokáig feledésbe merült és most többen is újrafelfedezték. M. Morse egy differenciál geometriai, E.S. Arshon egy lánctörtekkel kapcsolatos probléma vizsgálata során talált négyzetmentes sorozatot. Később P.S. Novikov és S.I. Adjan a csoportelméleti Burnside probléma megoldásában használta ezeket az eredményeket.
Thue tételének sokféle általánosítása született. A dolgozat egy ilyen általánosítást, egy gráfszínezési problémát vizsgál. Tekintsünk egy gráfot, és csúcsainak egy színezését. Azt mondjuk, hogy a színezés négyzetmentes, ha egy tetszőleges úton haladva a csúcsok színeit egymás mellé írva négyzetmentes sorozatot kapunk. Ha speciálisan kettő hosszú utakat tekintünk, akkor azt kapjuk, hogy a szomszédos csúcsok különböző színűek, tehát a négyzetmentes színezések jó színezések a klasszikus érelemben is. Thue tétele ebben a terminológiában azt állítja, hogy a végtelen hosszú útnak létezik négyzetmentes színezése 3 színnel. Négyzetmentes színezéseket először N. Alon és társszerzői vizsgáltak egy 2001-es cikkükben. Ők vetették fel azt a kérdést, hogy létezik-e olyan C egész szám, hogy minden síkgráf négyzetmentesen színezhető C színnel.
A dolgozat a kérdést megválaszolja egy szűkebb gráfosztály esetén, igazolja, hogy minden outterplanar gráf 12 színnel színezhető.

Kulcsszavak: gráfok, négyzetmentes színezés

 

SQUARE-FREE COLORING OF GRAPHS
Author: Varjú Péter, IVth year
Supervisor: Dr. Barát János, associate professor
Institute: University of Szeged, Faculty of Science, Mathematical Institute

In 1906. Axel Thue made an infinite sequence of the numbers 1, 2, 3, which has the property, that it does not contain two consecutive identical blocks i.e. there are no l and k such that al=al+k, al+1=al+k+1,… al+k-1=al+2k-1. Such sequences are called square-free sequences. This result has been forgotten and rediscovered several times. Square-free sequences were found by M. Morse during the examination of a differential geometric problem, and E.S. Arshon while he studied a problem of continued fractions. Later P.S. Novikov and S.I. Adjan used these results in the solution of the famous Burside problem of group theory.
There are a lot of generalizations of Thues's theorem. The paper examines such a generalization, a graph coloring problem. Consider a graph, and a coloring of its vertices. We say that this coloring is square-free, if we write down the sequence of colors of the vertices in any path, then we get a square-free sequence. Considering paths of length two, we find that the colors of adjacent vertices are different, thus square-free colorings are well-colorings in the classical sense. The theorem of Thue says that the infinite path has a square-free coloring with 3 colors. Square-free colorings were studied by N. Alon and his coauthors at the first time. In their paper from 2001., they posed the question whether there is an integer C such that any planar graph has a square-free coloring with C colors. The paper answer this question in the special case of outterplanar graphs, by showing that they are 12-colorable.

Keywords: graphs, square-free coloring