Goldberg's conjecture

Importance: High ✭✭✭
Author(s): Goldberg, Mark K.
Subject: Graph Theory
» Coloring
» » Edge coloring
Recomm. for undergrads: no
Posted by: mdevos
on: October 4th, 2008

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}

This important problem remains open despite considerable attention. The same conjecture was independently discovered by Andersen and Seymour.

Vizing's Theorem, one of the cornerstones of graph colouring, shows that $\chi'(G) \le \Delta(G) + 1$ for every simple graph $G$. So, in particular, every simple graph satisfies Goldberg's conjecture. Graphs with parallel edges need not satisfy Vizing's bound. For instance, if $G$ is the graph obtained from a triangle by adding an extra $k-1$ edges in parallel with each existing one, then $\Delta(G) = 2k$ but $\chi'(G) = 3k$. More generally, if $H$ is a subgraph of $G$, then every colour can appear on at most $\lfloor \frac{1}{2}|V(H)| \rfloor$ edges of $H$, so $\chi'(G) \ge |E(H)| / \lfloor \tfrac{1}{2} |V(H)| \rfloor $. Thus, $w(G)$, our overfull parameter, is a natural lower bound on $\chi'(G)$, and Goldberg's conjecture asserts that whenever $\chi'(G)$ exceeds $\Delta(G)+1$, then it is equal to this lower bound.

Although the statement of the conjecture may appear to be the most natural formulation, there are a couple of related conjectures with similar lower bounds. For instance, \OPrefnum[Seymour's r-graph conjecture]{2226} is equivalent to the statement that $\chi'(G) \le \max \{\Delta(G), w(G) \} + 1$. Goldberg also conjectured that $\chi'(G) \le \max\{ \Delta(G), w(G) + 1\}$.

In addition to simple graphs, Goldberg's Conjecture is known to hold for any graph $G$ which satisfies one of the following \begin{itemize} \item $\Delta(G) \le 11$ \item $G$ has no minor isomorphic to $K_5$ minus an edge. \item $\Delta(G)$ is sufficiently large in comparison with $|V(G)|$. \end{itemize}


Packers And Movers Chandigarh
Packers And Movers Hyderabad
Packers And Movers Bangalore


*[G] M. K. Goldberg, Multigraphs with a chromatic index that is nearly maximal. (Russian) A collection of articles dedicated to the memory of Vitaliĭ Konstantinovič Korobkov. Diskret. Analiz No. 23 (1973), 3--7, 72. \MRhref{MR0354429}

* indicates original appearance(s) of problem.

Latest Developments

Stiebitz et al(2006), Yu(2008) and Kurt(2009) has separately shown $\chi'(G) \geq \Delta+\sqrt{\Delta/2}$ implies Goldberg Conjecture. While Yu's method gives a methodological approach to the general problem, Kurt provides a very short and elementary proof.

Scheide (2008) has shown $\chi'(G)>\frac{15}{14}\Delta+\frac{12}{14}$ implies the Goldberg Conjecture.

Kurt(2009) has shown $\chi'(G)>\frac{17}{16}\Delta+\frac{14}{16}$ implies the Goldberg Conjecture.

Different Goldberg Conjecture?


Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.