Upperbound for difference between chromatic number &#x03C7;<!-- χ

Jaime Coleman

Jaime Coleman

Answered question

2022-05-13

Upperbound for difference between chromatic number χ ( G ) and list-chromatic number χ L ( G )

Answer & Explanation

partyjnopp9wa

partyjnopp9wa

Beginner2022-05-14Added 17 answers

Step 1
The gap between χ and χ L can be arbitrarily large. A construction for seeing this is provided in a survey paper by Alon. In summary, given a complete bipartite graph, then its chromatic number is clearly equal to 2.
Step 2
However, for any k 2, there are bipartite graphs whose list-chromatic number exceeds k.
There is a famous conjecture given independently by various researchers such as Vizing or Tucker.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?