Note on a conjecture of Toft (Q1900186)

A subdivision \(H\) of \(K_n\) is any graph obtained by replacing some edges \(uv\) by a \(uv\) path (whose internal vertices are then of degree two in \(H\)). The subdivision is said to be fully odd if every added path has an odd number of edges. \textit{B. Toft} [Recent advances in graph theory, 543-544 (1975)] conjectured that every 4-critical graph contains a fully odd subdivision of \(K_4\). The present authors show that if a graph \(G\) has a degree-three vertex \(v\) such that \(G\)-\(v\) is 3-colorable, then either \(G\) is 3-colorable or it contains a fully odd \(K_4\). Thus Toft's conjecture is affirmed for the case of 4-critical graphs with a vertex of degree three. The authors then use this special case to prove Toft's conjecture for line graphs. The constructive proof yields a polynomial algorithm which, for a given 3-degenerate graph (every subgraph has a vertex of degree three or less), either finds a 3-coloring or exhibits a subgraph that is a fully odd \(K_4\).