Covers and cores of r-graphs
Final Report Abstract
There are many hard problems in graph theory which are equivalent to their restriction on cubic graphs. Examples of such problems are Tutte's 5-ow Conjecture (1954), the Cycle Double Cover Conjecture (1973), the Berge-Fulkerson Conjecture (1971) and the conjecture of Fan and Raspaud (1994). These conjectures are trivially true for cubic graphs with edge-chromatic number 3. A snark is a bridgeless cubic graph with edge-chromatic number 4. Hence, it suces to prove the aforementioned conjectures for snarks. Snarks are also closely related to the Four Color Theorem which is equivalent to the statement that there is no planar snark. There are many parameters that measure how far a snark is from being 3-edge colorable. These parameters are also called measures of edge-uncolorability. The main motivation for the study of these parameters is to gain new insight into the structure of snarks and to prove some of the aforementioned conjectures for some specic snarks. The notion of cores of cubic graphs was introduced by Steffen [E. Steffen, 2015], which was the starting point of the project. Let G be a bridgeless cubic graph and S be a list of three 1-factors of G. For i ∈ {0, 1, 2, 3} let Ei be the set of edges which are in precisely i elements of S . The core Gc of G with respect to S is the subgraph which is induced by E0 ∪ E2 ∪ E3 . Let µ3 (G) be the minimum |E0 | over all lists of three 1-factors of G. Clearly, µ3 is a measure of edge-uncolorability which is closely related to cores in cubic graphs. In terms of cores, the Fan-Raspaud conjecture states that every bridgeless cubic graph has a cyclic core, that is the components of the core are (even) circuits. A surprising result of the project was that the seemingly weaker conjecture that every snark has a bipartite core is equivalent to the Fan-Raspaud conjecture. The Fan-Raspaud-Conjecture is also equivalent to the 4-line Fano-flow conjecture. The notion of cores is generalized to weak cores, and it is proved that there is an equivalent formulation of the 5-line Fano-flow conjecture in terms of weak cores. Hence, a clear picture is achieved how the concepts of cores, Fano-flow conjectures, and coverings are related to each other. It is proved that every 3-edge-connected cubic graph G without non-trivial 3-edge cuts has a cyclic core if µ3 (G) ≤ 9. A result that gives some support to the truth of the Fan-Raspaud conjecture. Furthermore, it is shown that µ3 dominates many other measures of edge-uncolorability. Similar results are obtained for the measure of edge-uncolorability which is related to weak cores. The Petersen coloring conjecture plays a distinguished role in this research context since its truths would imply the truth of many of the aforementioned conjectures. Jaeger proved that it is equivalent to the statement that every bridgeless cubic graph has a normal 5-edge coloring. It is shown that every bridgeless cubic graph G has a normal 5-edge coloring where all but µ3 (G) edges are normal. For r-graphs, the fraction of edges of an r-graph which can be covered by k 1-factors is studied. Results of Kaiser, Král, Norine and Mazzuoccolo for cubic graphs are generalized to r-graphs. We propose a very natural generalization of the Fan-Raspaud conjecture to r-graphs, which is shown to be equivalent to the statement that every r-graph has an Eulerian core.
Publications
- Cores, joins and the Fano-Flow conjectures, to appear in Discuss. Math. Graph Theory
L. Jin, G. Mazzuoccolo and E. Steffen
(See online at https://doi.org/10.7151/dmgt.1999) - Face-degree bounds for planar critical graphs, Electron. J. Combin. 23(3) (2016)
L. Jin, Y. Kang and E. Steffen
- Remarks on planar edge-chromatic critical graphs, Discrete Applied Math. 200 (2016) 200-202
L. Jin, Y. Kang and E. Steffen
(See online at https://doi.org/10.1016/j.dam.2015.07.007) - Covers and cores of r-graphs, Dissertation, Faculty for Electrical Engineering, Computer Science, and Mathematics (Institute for Mathematics), Paderborn University, July 2017
L. Jin
(See online at https://dx.doi.org/10.17619/UNIPB/1-152) - On measures of edge-uncolorability of cubic graphs: A brief survey and some new results, (2017)
M.A. Fiol, G. Mazzuoccolo, E. Steffen
- Petersen cores and the oddness of cubic graphs, J. Graph Theory 84 (2017) 109-120
L. Jin and E. Steffen
(See online at https://doi.org/10.1002/jgt.22014)
