Note on a conjecture of Toft
type: Item
instance of: scholarly article
title: Note on a conjecture of Toft
zbMATH Open document ID: 0832.05038
DOI: 10.1007/BF01299743
author: T. R. Jensen
author: F. Bruce Shepherd
published in: Combinatorica
publication date: 1996-02-08T00:00:00Z
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\).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 806478
zbMATH Keywords: conjecture of Toft
zbMATH Keywords: subdivision
zbMATH Keywords: fully odd subdivision
zbMATH Keywords: line graphs
zbMATH Keywords: polynomial algorithm
Wikidata QID: Q123245427
reviewed by: Arthur T. White
MaRDI profile type: Publication
cites work: Hajos' graph-coloring conjecture: Variations and counterexamples
cites work: On certain polytopes associated with graphs
cites work: A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
cites work: Q3853641
cites work: Q5732334
cites work: Some simplified NP-complete graph problems
cites work: Matrices with the Edmonds-Johnson property
cites work: Small graphs with chromatic number 5: A computer search
cites work: Note to a problem of T. Gallai and G. A. Dirac
cites work: 4-critical 4-valent planar graphs constructed with crowns.
cites work: Q3214947
cites work: Q5675743
cites work: Gallai's problem on Dirac's construction
Recommended article: A note on Toeplitz' conjecture
Recommended article: On a conjecture of Thomassen and Toft
Recommended article: Q5880867
Recommended article: A note on a conjecture of T. H. Foregger
Recommended article: A note on Feichtinger conjecture
Recommended article: Q3689194
Recommended article: Q4237727
Recommended article: Note on a conjecture of Sierksma
Recommended article: Remarks on a conjecture of Barát and Tóth
Recommended article: Notes to the Feit-Thompson conjecture
description: scientific article; zbMATH DE number 806478