## DIMACS TR: 93-63

## A Note on a Conjecture of Toft

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

**
ABSTRACT
**

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