DIMACS TR: 2008-03

Classes of 3-regular graphs that are (7,2)-edge-choosable

Authors: Daniel W. Cranston and Douglas B. West


A graph is (7,2)-edge-choosable if, for every assignment of lists of size 7 to the edges, it is possible to choose two colors for each edge from its list so that no color is chosen for two incident edges.  We show that every 3-edge-colorable graph is (7,2)-edge-choosable and also that many non-3-edge-colorable 3-regular graphs are (7,2)-edge-choosable.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2008/2008-03.ps.gz
DIMACS Home Page