Non-conformable subgraphs of non-conformable graphs
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.
- Totally critical even order graphs
- The structure of totally critical graphs of odd order
- A note on total chromatic numbers of graphs
- The overfull conjecture and the conformability conjecture
- Results about the total chromatic number and the conformability of some families of circulant graphs
- On the conformability of regular line graphs
- A polynomial-time algorithm for conformable coloring on regular bipartite and subcubic graphs
This page was built for publication: Non-conformable subgraphs of non-conformable graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1849925)
