Duration: 01. 10. 2021―30. 09. 2024
Financed by: Slovenian Research Agency (ARRS)
Project type: Research project
Project description:
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.
Project leader: prof. Riste Škrekovski PhD
