The *overfull parameter* is defined as follows:

**Conjecture**Every graph satisfies .

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 for every simple graph . So, in particular, every simple graph satisfies Goldberg's conjecture. Graphs with parallel edges need not satisfy Vizing's bound. For instance, if is the graph obtained from a triangle by adding an extra edges in parallel with each existing one, then but . More generally, if is a subgraph of , then every colour can appear on at most edges of , so . Thus, , our overfull parameter, is a natural lower bound on , and Goldberg's conjecture asserts that whenever exceeds , 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, Seymour's r-graph conjecture is equivalent to the statement that . Goldberg also conjectured that .

In addition to simple graphs, Goldberg's Conjecture is known to hold for any graph which satisfies one of the following

- \item \item has no minor isomorphic to minus an edge. \item is sufficiently large in comparison with .

Packers And Movers Chandigarh

Packers And Movers Hyderabad

Packers And Movers Bangalore

## Bibliography

*[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. MathSciNet

* indicates original appearance(s) of problem.