Home » Subject » Graph Theory » Coloring » Edge coloring

List colorings of edge-critical graphs

Importance: Medium ✭✭
Author(s): Mohar, Bojan
Subject: Graph Theory
» Coloring
» » Edge coloring
Keywords: edge-coloring
list coloring
Recomm. for undergrads: no
Posted by: Robert Samal
on: June 12th, 2007
Conjecture   Suppose that $ G $ is a $ \Delta $-edge-critical graph. Suppose that for each edge $ e $ of $ G $, there is a list $ L(e) $ of $ \Delta $ colors. Then $ G $ is $ L $-edge-colorable unless all lists are equal to each other.

(Reproduced from [M].)

A graph $ G $ is said to be $ \Delta $-edge-critical if it is not $ \Delta $-edge-colorable but every edge-deleted subgraph is $ \Delta $-edge-colorable. (Here $ \Delta $ is the maximum degree of $ G $.)

Bibliography

*[M] B. Mohar, Problem of the Month


* indicates original appearance(s) of problem.
add new comment