DIMACS TR: 96-41
A corrected version of the Duchet Kernel Conjecture
Authors: E. Boros, V. Gurvich
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:
DIMACS Home Page