96-41: A corrected version of the Duchet Kernel Conjecture

DIMACS TR: 96-41

A corrected version of the Duchet Kernel Conjecture

Authors: E. Boros, V. Gurvich

ABSTRACT
In 1980 Piere Duchet conjectured that odd directed cycles are the only edge minimal kernel-less connected digraphs i.e. in which after the removal of any edge a kernel appears. Although this conjecture was disproved recently by Apartsin, Ferapontova and Gurvich (1996), the following modification of Duchet's conjecture still holds: odd holes (i.e. odd non-directed chordless cycles of length 5 or more) are the only connected graphs which are not kernel-solvable but after the removal of any edge the resulting graph is kernel-solvable.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-41.ps.gz

DIMACS Home Page