The total coloring conjecture, attributed independently to Mehdi Behzad and Vadim Vizing between 1964 and 1968, states that the total chromatic number of a graph G, the fewest colors needed to properly color its vertices and edges together, is at most two more than its maximum degree. The conjecture is known to hold for all bipartite graphs and most planar graphs, but remains open in general.
Facts
StatementFor every graph G, the total chromatic number of G is at most the maximum degree of G plus 2. 1 Progress Toward ResolutionThe conjecture is known to hold for all bipartite graphs and for most planar graphs. In general the total chromatic number of any graph is known to be at most its maximum degree plus 10 to the 26th power, a bound due to Molloy and Reed in 1998; for graphs of sufficiently large maximum degree this was improved to at most the maximum degree plus 8 times the natural log of the maximum degree raised to the 8th power. The general conjecture remains open. 1 Classification
Resolution Status Prize Status
Prize Status (category) Connections
In Branch
Source Total Coloring (Wikipedia)
Sources
1. Total Coloring (Wikipedia)
Total coloring conjecture section
χ ″ ( G ) ≤ Δ ( G ) + 2
Known upper bounds section
χ ″ ( G ) ≤ Δ ( G ) + 10^26
- Lead section
In Branch: Graph Theory, Lead sentence
In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.