The list coloring conjecture, in graph theory, concerns list edge-coloring, a form of graph coloring that combines list coloring and edge coloring. A graph is k-edge-choosable if, whenever every edge is given a list of at least k allowed colors, a proper edge coloring can always be chosen from those lists. The list chromatic index of a graph is the smallest k for which this holds, and the list coloring conjecture states that this list chromatic index always equals the graph's ordinary chromatic index. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Progress Toward ResolutionThe list chromatic index and the ordinary chromatic index have been shown to agree asymptotically, though the full conjecture that they are always equal remains open. 2 Classification
Resolution Status Prize Status
Prize Status (category) Connections
In Branch
Source List edge-coloring (Wikipedia)
Sources
1. List Coloring Conjecture (Wikipedia)
Wikimedia FoundationLead section
It is conjectured that it always equals the chromatic index.
List coloring conjecture section, opening statement
The most famous open problem about list edge-coloring is probably the list coloring conjecture.
View the Source 2. List Coloring Conjecture (Wikipedia)
Current status section, asymptotic resultQuote, Current status section, asymptotic result
the list chromatic index and the chromatic index agree asymptotically
List edge-coloring (Wikipedia)
In Branch: Graph Theory, Lead sentenceQuote, In Branch: Graph Theory, Lead sentence
In graph theory, list edge-coloring is a type of graph coloring that combines list coloring and edge coloring.
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.