Goldberg, Mark K.

Goldberg's conjecture ★★★

Author(s): Goldberg

The overfull parameter is defined as follows:

$w(G) = \max_{H \subseteq G} \left\lceil \frac{ |E(H)| }{ \lfloor \tfrac{1}{2} |V(H)| \rfloor} \right\rceil.$

Conjecture Every graph $G$ satisfies $\chi'(G) \le \max\{ \Delta(G) + 1, w(G) \}$ .

Posted by mdevos
updated February 6th, 2009