Non-conformable subgraphs of non-conformable graphs (Q1849925)

A total coloring assigns a color to each vertex and edge of a graph so that adjacent or incident elements receive distinct colors. Let \(\Delta(G)\) denote the maximum degree of a graph \(G\), so \(\Delta(G)+1\) is an obvious lower bound on the number of colors in a total coloring. The total coloring conjecture asserts that any graph can be totally colored in \(\Delta(G)+2\) colors. The deficiency of a graph is \(\text{def}(G)=\Delta(G)|V(G)|-2|E(G)|\). It is a measure of how far a graph is from being regular, and hence in a sense how difficult it is to totally color the graph with \(\Delta(G)+1\) colors. A graph is conformal if it has a proper vertex-coloring in \(\Delta(G)+1\) colors such that the number of color classes whose parity is not the same as \(|V(G)|\) is at most \(\text{def}(G)\) (some classes may be empty). A quick lemma establishes that a conformal graph has a total coloring in \(\Delta(G)+1\) colors, so non-conformal graphs are important to the total coloring conjecture. The conformability conjecture characterizes the graphs with \(\Delta(G) \geq \lceil |V(G)|/2\rceil\) whose total coloring number is \(\Delta(G)+1\) in terms of their non-conformable subgraphs. The authors prove that if \(G\) is a non-conformable graph with \(\Delta(G) \geq \lceil |V(G)|/2\rceil\), and \(H\) is a non-conformable subgraph of \(G\) with the same maximum degree, then \(H\) spans \(G\). They also give examples that show the inequality bounding \(\Delta(G)\) is best possible.