Covers and cores of r-graphs

• Applicant: Professor Dr. Eckhard Steffen
• Subject Area: Mathematics
• Term: from 2013 to 2017
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 240639532

There are many hard problems in graph theory which can be solved in the general case if they can be solved for cubic graphs. Examples of such problems are the 4-color-problem (now a theorem), problems concerning cycle- and matching-covers, surface embeddings or flow-problems on graphs. The majority of these problems is easy to solve for 3-edge-colorable cubic graphs. Hence, the class of bridgeless non-3-edge-colorable graphs (so called snarks) is the class of possible counterexamples to many hard conjectures. One major difficulty in proving theorems for snarks is to find/define appropriate structural parameters for a proof. There are many papers dealing with reductions of snarks to smaller graphs or with invariants that "measure" how far a snark is from being 3-edge-colorable. Many positive results on the aforementioned problems are proved for snarks that satisfy some additional conditions with respect to one of these invariants. In [52] we introduce the core of a cubic graph. Let G be a cubic graph, M_1, M_2 and M_3 be three pairwise different 1-factors of G. Let M be the set of edges which are in more than one and U be the set of edges which are not contained in any of the three 1-factors, and let k = |U|. The k-core of G with respect to M_1, M_2, and M_3 is the subgraph G_c of G which is induced by the union of M and U. The study of k-cores gives surprising new insights into the structure of snarks. Let r be a positive integer. An r-graph is an r-regular graph where for every vertex set S of odd cardinality there are at least r edges with precisely one end in S. The objective of the proposed research project is to develop a theory of cores for r- graphs. First, we will focus on cubic graphs. The conjectures of Berge-Fulkerson, Fan and Raspaud, the cycle-double-cover conjecture and shortest cycle covers of cubic graphs will be studied. Some of these conjectures can be reformulated in terms of cores. But there are some natural statements on cores which are weaker than these conjectures. One objective of the proposed project is to achieve results on these conjectures. Further, the results for cubic graphs should be extended to r-graphs. These results should be used to prove some results for the generalized Berge-Fulkerson- and the r-graph-conjecture of Seymour. Furthermore, results about cores of r-graphs should be used to prove statements about decompositions of multigraphs with huge chromatic index.

• DFG Programme: Research Grants