Univerza na Primorskem Fakulteta za matematiko, naravoslovje in informacijske tehnologije
Več informacij o projektu / More info about the project
Vsebina projekta / Project content
Projekt se osredotoča na nekatere vidike kromatične teorije grafov, znanstvenega področja, ki je od skromnih začetkov v zadnjem stoletju doživelo izjemno rast in doseglo precejšnjo globino. Dandanes velja za eno glavnih področij raziskav v matematiki.
Pravilno barvanje povezav (tj. barvanje povezav, tako da sosednje povezave prejmejo različne barve) kubičnih grafov predstavlja bistveni del kromatične teorije grafov, ki je tesno povezan z zgodovino njenega razvoja. Obsežne raziskave potekajo že več kot stoletje. Prvotna motivacija izhaja iz Taitovega poskusa rešitve slavnega Problema štirih barv, v naslednjih desetletjih pa je koncept vzpostavil tesne povezave z drugimi področji teorije grafov. Barvanje povezav deli kubične grafe na dva neenaka dela: razred Taitovo-obarvljivih (po povezavah 3-obarvljivih) grafov obsega skoraj vse kubične grafe, medtem ko je njegov komplement majhen razred grafov, ki potrebujejo 4 barve in za katere je znano, da so tesno povezani s številnimi izjemno težkimi problemi.
Netrivialni člani slednje družine, imenovani snarki, lahko vključujejo protiprimere za Berge-Fulkersonovo domnevo in Domnevo o Petersenovem barvanju. Naše predvidene raziskave se osredotočajo na tri razširitve koncepta Taitovih barvanj, ki so močno povezane z omenjenima dvema zloglasnima domnevama; in sicer Fanovo barvanje, normalno barvanje povezav in krepko barvanje povezav.
Številni problemi, ki vključujejo kubične grafe, se nanašajo na obstoj popolnih prirejanj, katerih presek je majhen ali prazen, kar je naravno, saj je obstoj dveh disjunktnih popolnih prirejanj ekvivalenten Taitovemu barvanju. Fan-Raspaudova domneva pravi, da vsak 2-povezan kubični graf vsebuje 3 popolna prirejanja s praznim presekom. Ta poenostavitev Berge-Fulkersonove domneve se je nedavno pojavila v kontekstu Fanovih barvanj, posplošitve 3-barvanja povezav, ki točkam Fanove ravnine dodeljujejo povezavam kubičnega grafa tako, da so barve vsakih treh povezav s skupnim krajiščem tvorijo premico. Eden od ciljev naše raziskave je nadaljevanje študij o najmanjšem številu premic, ki se pojavijo kot barvni vzorci okoli vozlišč. V tem smislu je Fanovo barvanje z 1 premico Taitovo, medtem ko je Fanovo barvanje s 4 premicami ekvivalentno Fan-Raspaudovim popolnim prirejanjem.
Še eno posplošitev pravilnih barvanj povezav dobimo z nadomestitvijo globalnega pogoja glede števila barv z lokalnim. Ekvivalentna oblika Domneve o Petersenovem barvanju pravi, da vsak 2-povezan kubični graf dopušča pravilno barvanje povezav s 5 barvami, tako da so sosede vsake povezave pobarvane z 2 (revna povezava) ali 4 (bogata povezava) barvami; takšno barvanje imenujemo normalno. Ta oblika omogoča druge pristope k Petersenovem barvanju, tako da dovoli uporabo več ali manj kot 5 barv, in da je pogoj normalnosti izpolnjen na velikem delu povezav.
Pravilno 3-barvanje povezav kubičnega grafa je barvanje, pri katerem je vsaka povezava revna. Na drugi strani imamo krepko barvanje povezav, pri katerih je vsaka povezava bogata. Zadnje barvanje tvori tretjo smer našega projekta. Določanje zgornjih mej za krepko barvanje povezav splošnih grafov je še vedno aktualna in splošno raziskovana tema, reševanje vprašanj v zvezi s kubičnimi grafi pa nas bo približalo k rešitvi splošnega primera.
Glavni cilj projekta je (delno) razrešiti zgoraj omenjene probleme s preučevanjem kubičnih grafov pod določenimi predpostavkami. Izboljšali bomo obstoječe in razvili nove tehnike dokazovanja ter izboljšali razumevanje teh problemov.
Rezultati projekta bodo pomembno vplivali na skupnost raziskovalcev barvanj grafov, saj so opisane domneve in njihove izpeljanke predmet številnih raziskav.
The project concentrates on certain aspects of chromatic graph theory, a scientific area which from its modest outsets, has undergone tremendous growth and reached considerable depth in the last century. Nowadays, it is considered as one of the main areas of research within mathematics.
Proper edge-colorings (i.e., colorings of edges such that adjacent edges receive distinct colors) of cubic graphs form an essential part of chromatic graph theory that is intimately related to the history of its development. They have been extensively studied for more than a century. The original incentive came from Tait’s attempt to solve the famous Four-Color Problem, and during the subsequent decades the concept has established close connections to other areas of graph theory. Edge-colorings divide cubic graphs into two uneven parts: the class of Tait-colorable (3-edge-colorable) graphs comprises almost all cubic graphs, whereas its complement is an extremely sparse class of graphs needing 4 colors and known to being closely related to a number of exceedingly difficult problems. Non-trivial members of the latter family, called snarks, may include counterexamples to the Berge-Fulkerson Conjecture and the Petersen Coloring Conjecture. Our intended research focuses on three extensions of the concept of Tait coloring which are strongly connected to mentioned two notorious conjectures; namely, Fano coloring, normal edge-coloring, and strong edge-coloring.
A number of problems involving cubic graphs concerns the existence of perfect matchings whose intersection is small or empty, which is natural as the existence of two disjoint perfect matchings is equivalent to Tait colorability. The Fan-Raspaud Conjecture asserts that every bridgeless cubic graph contains 3 perfect matchings with empty intersection. This relaxation of the Berge-Fulkerson Conjecture has recently reappeared in the context of Fano colorings, a generalization of proper 3-edge-colorings assigning points of the Fano plane to the edges of cubic graph subjected to the condition that the colors of any three edges meeting at a vertex form a line. One of the objectives of our research is a continuation of an ongoing study regarding the minimum number of lines appearing as color patterns around the vertices. In this sense, a 1-line Fano coloring is a Tait coloring, whereas a 4-line Fano coloring is equivalent to the existence of a Fan-Raspaud tripod of perfect matchings.
Another generalization of proper edge-colorings is obtained by replacing the global condition on the number of colors by a local one. An equivalent formulation of the Petersen Coloring Conjecture states that every bridgeless cubic graph admits a proper edge-coloring with 5 colors such that for every edge, the set of colors assigned to its adjacent edges has cardinality either 2 (poor edge) or 4 (rich edge); such a coloring is called normal. This formulation enables alternate approaches to Petersen colorings by allowing more or less than 5 colors globally, and asking that the normality condition is satisfied on a large proportion of the edge set.
A proper 3-edge-coloring of a cubic graph is precisely a normal coloring in which every edge is poor. On the other hand, strong edge-colorings are proper edge-colorings in which every edge is rich. This topic forms the third aspect of our project. Determining upper bounds
for strong edge-coloring of general graphs is still a broadly studied topic, and resolving the questions concerning cubic graphs will bring us closer to resolving the general case.
The main goal of the project is to (partially) resolve the above problems by studying cubic graphs under specific assumptions. We will also improve existing and develop new proof techniques, and increase understanding of these problems in general. Project results will have an important impact to graph coloring community as the conjectures and their derivatives are a subject of constant investigation of many researchers.