Note on a conjecture of Toft

DOI10.1007/BF01299743MaRDI QIDQ1900186zbMATH OpenWikidataFDO

Authors T. R. Jensen, F. Bruce Shepherd

Publication date 8 February 1996

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01299743

zbMATH Keywords

conjecture of Toftfully odd subdivisionline graphspolynomial algorithmsubdivision

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

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\).

Recommendations

• A note on Toeplitz' conjecture
• On a conjecture of Thomassen and Toft
• A note on the Koethe conjecture
• A note on a conjecture of T. H. Foregger
• A note on Feichtinger conjecture
• scientific article; zbMATH DE number 3912388
• scientific article; zbMATH DE number 1275149
• Note on a conjecture of Sierksma
• Remarks on a conjecture of Barát and Tóth
• Notes to the Feit-Thompson conjecture

Cites work

• 4-critical 4-valent planar graphs constructed with crowns.
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• Gallai's problem on Dirac's construction
• Hajos' graph-coloring conjecture: Variations and counterexamples
• scientific article; zbMATH DE number 3427388 (Why is no real title available?)
• scientific article; zbMATH DE number 3654142 (Why is no real title available?)
• scientific article; zbMATH DE number 3409385 (Why is no real title available?)
• scientific article; zbMATH DE number 3195967 (Why is no real title available?)
• Matrices with the Edmonds-Johnson property
• Note to a problem of T. Gallai and G. A. Dirac
• On certain polytopes associated with graphs
• Small graphs with chromatic number 5: A computer search
• Some simplified NP-complete graph problems

Cited in

(5)

• Odd-\(K_{4}\)'s in stability critical graphs
• Proof of Toft's conjecture: Every graph containing no fully odd K₄ is 3-colorable
• On the multiple Borsuk numbers of sets
• Crumby colorings -- red-blue vertex partition of subcubic graphs regarding a conjecture of Thomassen
• scientific article; zbMATH DE number 1222840 (Why is no real title available?)

This page was built for publication: Note on a conjecture of Toft

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1900186)