Gráfszínezések és gráfok felbontásai  részletek

súgó  nyomtatás 
vissza »

 

Projekt adatai

 
azonosító
75837
típus PD
Vezető kutató Barát János
magyar cím Gráfszínezések és gráfok felbontásai
Angol cím Colorings and decompositions of graphs
magyar kulcsszavak gráf, színezés, felbontás, homomorfizmus
angol kulcsszavak graph, coloring, decomposition, homomorphism
megadott besorolás
Matematika (Matematikai, Fizikai, Kémiai és Mérnöki Tudományok)60 %
Ortelius tudományág: Kombinatorika
Számítástudomány (Matematikai, Fizikai, Kémiai és Mérnöki Tudományok)40 %
zsűri Matematika–Számítástudomány
Kutatóhely Rendszer-és Számítástudományi Tanszék (Pannon Egyetem)
projekt kezdete 2008-10-01
projekt vége 2011-10-31
aktuális összeg (MFt) 17.590
FTE (kutatóév egyenérték) 2.42
állapot lezárult projekt
magyar összefoglaló
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.
angol összefoglaló
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.





 

Zárójelentés

 
kutatási eredmények (magyarul)
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
kutatási eredmények (angolul)
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
a zárójelentés teljes szövege https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=75837
döntés eredménye
igen





 

Közleményjegyzék

 
Barát J, Wood DR: Notes on nonrepetitive graph colouring, Electron J Combin 15: R99, p.13, 2008
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, Stojakovic M: On winning fast in Avoider-Enforcer games, Electron J Combin 17: R56 p.12., 2010
Barát J, Tóth G: Towards the Albertson conjecture, Electron J Combin 17: R73, p.15., 2010
Barát J, Kriesell M: What is on his mind?, Discrete Math 310: 2573-2583., 2010
Barát J, Hajnal P, Horváth EK: Elementary proof techniques for the maximum number of islands., Eur J Combin 32: 276-281, 2011
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
Barát J, Hajnal P, Lin Y, Yang A: On the structure of graphs with path-width at most two, Stud Sci Math Hung: p.12., 2012
Barát J, Füredi Z, Kantor I, Kim Y, Patkós B: Large B_d-free and union-free subfamilies, SIAM J Disc Math: p.8., 2011
Barát J, Czap J: Vertex coloring of plane graphs with nonrepetitive boundary paths, J Graph Theor: p.8., 2012
Barát J, Gebner D: Edge-decomposition of graphs into copies of a tree with four edges, J Graph Theory: p.12., 2012
Barát J, Joret G, Wood DR: Disproof of the List Hadwiger Conjecture, Electron J Comb: p.7., 2011




vissza »