Home » Keyword index

multigraph


Graph Theory » Coloring » Edge coloring

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) \} $.

Keywords: edge-coloring; multigraph

Posted by mdevos
updated June 5th, 2013
2 comments
Syndicate content