DIMACS TR: 93-63

A Note on a Conjecture of Toft

Authors: T.R. Jensen, F.B. Shepherd


A conjecture of Toft asserts that any 4-critical graph contains a fully odd subdivision of K4 (each edge replaced by an odd path). It is shown that if a graph G has a degree three node v such that G-v is 3-colourable, then either G itself is 3-colourable or G contains a fully odd K4. This resolves Toft's conjecture in the special case of 4-critical graphs with a degree three node. This is in turn used to verify the conjecture for line graphs. The proof is constructive and yields an algorithm (polytime) for so-called 3-degenerate graphs to either find a 3-colouring or a fully odd K4 subgraph.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-63.ps
DIMACS Home Page