Department of Computer Science and Systems Technology (University of Pannonia)
Starting date
2008-10-01
Closing date
2011-10-31
Funding (in million HUF)
17.590
FTE (full time equivalent)
2.42
state
closed project
Summary in Hungarian
Gráfok különböző színezése a gráfelmélet sokat vizsgált területe. A klasszikus csúcsszínezési probléma mellett, elméleti és alkalmazhatósági indokok miatt sok variáns jelent meg. Számelméleti érdekessége és a véletlen módszer alkalmazhatósága miatt kezdték el vizsgálni a nem-ismétlő (négyzetmentes) színezéseket. Ezen témában sikerült értékes eredményeket elérnünk Varjú Péterrel. Többek között megmutattuk, hogy a korlátos fa-szélességű gráfok véges sok színnel színezhetők négyzetmentesen. Ebben a témakörben célunk korlátos maximum fokú gráfok vizsgálata. Továbbá olyan színezések megadása, amelyek nem csak utak mentén, hanem minden séta mentén nem-ismétlő sorozatot adnak. Ennek kidolgozása David Wooddal közös munka.
A fent említett témáról tartottam előadást egy konferencián 2004-ben. Ekkor merült fel Pavol Hell-ben, hogy érdemes lenne vizsgálni olyan csúcsszínezéseket, melyek homomorfizmus-mentesek. Tehát adott G gráf esetén az a kérdés, hogy hány színre van szükség ahhoz, hogy G egyetlen színtartó homomorfizmusa az identitás legyen. Azon gráfok, amelyekre ez a színszám 1, éppen a merev gráfok. Gráfhomomorfizmusok és merev gráfok két nagy szakértője Pavol Hell és Jarik Nesetril. Utóbbival találkoztam 2007-ben egy szegedi konferencián. Akkor határoztuk meg, hogy milyen kérdések eldöntése lenne fontos ezen paraméterrel kapcsolatban. Többek között annak vizsgálata, hogy mennyire térhet el a ''distinguishing number''-től, melyet már 10 éve kutatnak.
A gráfok felbontásai szintén élénket tanulmányozott, népszerű kérdéskör. Carsten Thomassennel vetettük fel azt a kérdést, hogy milyen összefüggőségi feltétel garantál egy kívánt felbontást. Ezzel kapcsolatban vizsgáltuk a karomfelbontást (karom=3 élű csillag). Sejtésünk, hogy van olyan pozitív egész k, hogy minden k-él-összefüggő, 0 mod 3 élű gráf élei felbonthatók karmok uniójára. Bár ezt nem sikerült igazolni, de érdekes kapcsolatot találtunk Tutte 3-folyam problémájával. Jelen projekten belül az a célunk, hogy a 3 élű utakra történő felbontás létezésére adjunk elégséges összefüggőségi feltételt.
Summary
Coloring is an intensively studied field of graph theory. Beside the classical vertex coloring (4color theorem), many variants were created due to theoretical reasons and applications. Non-repetitive colorings were introduced for its number theoretical relation. The object is to color the vertices of the graph so that sequence of colors along any path is non-repetitive (e.g. not 234234). Together with Peter Varju, we achieved some results in this field. Among other things, we proved that graphs with bounded tree-width can be path-non-repetitively colored with a finite number of colors. Now, we target graphs with bounded maximum degree and try to generalize the results to walk-non-repetitive colorings. This research plan is joint with David Wood.
Influenced by one of my talks, in 2004 Pavol Hell asked if homomorphism-free colorings are of interest. For a given graph G, we ask the minimum number of colors to 'destroy' all color-preserving homomorphisms of G. The graphs, for which this number is 1 are known as rigid graphs. Two experts of graph homomorphisms and rigid graphs are Pavol Hell and Jarik Nesetril. I met the latter in a conference in Szeged in 2007. At that occasion we formulated some questions, whose decision would be crucial regarding this new parameter. One of them is to compare it to the distinguishing number, which have been studied for more than 10 years.
Graph-decompositions form a lively and popular area. Carsten Thomassen and myself posed the question, what degree of connectivity guaranties a desired decomposition. We have studied claw (a star with three edges) decompositions. We conjectured that there exists a constant k, such that each k-edge-connected graph with 0 mod 3 edges admits a claw decomposition. Despite failing to prove this conjecture, we found an interesting and tight connection to Tutte's 3-flow conjecture. This proposal focus on finding a sufficient connectivity condition, which implies a partition to paths with three edges.
Final report
Results in Hungarian
A nem-ismétlő színezéseket a véletlen módszer alkalmazhatósága miatt kezdték el vizsgálni.
Felső korlátot adtunk a színek számára, amely a maximum fok és a favastagság lineáris függvénye.
Olyan színezéseket is vizsgáltunk, amelyek egy síkgráf oldalain nem-ismétlők.
Sejtés volt, hogy véges sok szín elég. Ezt bizonyítottuk 24 színnel.
A kromatikus számot és a metszési számot algoritmikusan nehéz meghatározni. Ezért meglepő Albertson egy friss sejtése, amely kapcsolatot állít fel közöttük: ha egy gráf kromatikus száma r, akkor metszési száma legalább annyi, mint a teljes r csúcsú gráfé.
Bizonyítottuk a sejtést, ha r<3.57n, valamint ha 12
Results in English
Nonrepetitive colorings often use the probabilistic method.
We gave an upper bound as a linear function of the maximum degree and the tree-width.
We also investigated colorings, which are nonrepetitive on faces of plane graphs.
As conjectured, a finite number of colors suffice. We proved it by 24 colors.
The chromatic and crossing numbers are both difficult to compute.
The recent Albertson's conjecture is a surprising relation between the two:
if the chromatic number is r, then the crossing number is at least the crossing number of the complete graph on r vertices.
We proved this claim, if r<3.57n, or 12
Barát J, Hajnal P: Saturated tilings with dominoes and 2x2 squares, Proceedings of the 6th Japanese-Hungarian Symposium on Discrete Mathematics. Budapest, Magyarország, 2009.05.16-2009.05.19., p.9., 2009
Barát J, Korondi M, Varga V: How to dismantle an atomic cube in zero gravity, Proceedings of the 7th Hungarian-Japanese Symposium on Discrete Mathematics and its Applications, p.9., 2011
