Goldberg, Mark K.


Goldberg's conjecture ★★★

Author(s): Goldberg

The \emph{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. \]

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

Keywords: edge-coloring; multigraph

Syndicate content