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)
Posed By
Source Wolfram MathWorld: Total Coloring Conjecture - Wolfram MathWorld
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 SourceWolfram MathWorld: Total Coloring Conjecture - Wolfram MathWorld
Wolfram MathWorldPosed By: Vadim G. Vizing, Page textQuote, Posed By: Vadim G. Vizing, Page text
The total coloring conjecture, independently proposed by Behzad and Vizing, states that if
Reader 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.