Edge-coloring via fixable subgraphs

arXiv1507.05600MaRDI QIDQ6263776FDOQ6263776

Publication date: 20 July 2015

Abstract: Many graph coloring proofs proceed by showing that a minimal counterexample to the theorem being proved cannot contain certain configurations, and then showing that each graph under consideration contains at least one such configuration; these configurations are called emph{reducible} for that theorem. (A emph{configuration} is a subgraph

H

, along with specified degrees

d_{G} (v)

in the original graph

G

for each vertex of

H

.) We give a general framework for showing that configurations are reducible for edge-coloring. A particular form of reducibility, called emph{fixability}, can be considered without reference to a containing graph. This has two key benefits: (i) we can now formulate necessary conditions for fixability, and (ii) the problem of fixability is easy for a computer to solve. The necessary condition of emph{superabundance} is sufficient for multistars and we conjecture that it is sufficient for trees as well, which would generalize the powerful technique of Tashkinov trees. Via computer, we can generate thousands of reducible configurations, but we have short proofs for only a small fraction of these. The computer can write LaTeX code for its proofs, but they are only marginally enlightening and can run thousands of pages long. We give examples of how to use some of these reducible configurations to prove conjectures on edge-coloring for small maximum degree. Our aims in writing this paper are (i) to provide a common context for a variety of reducible configurations for edge-coloring and (ii) to spur development of methods for humans to understand what the computer already knows.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

This page was built for publication: Edge-coloring via fixable subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6263776)