摘要: A conjecture of Toft [17] asserts that any 4-critical graph (or equivalently, every 4-chromatic graph) contains a fully odd subdivision ofK4. We show if graphG has degree three nodev such thatG-v is 3-colourable, then eitherG 3-colourable or it oddK4. This resolves Toft's in the special case where node, which turn used to prove for line-graphs. The proof constructive and yields polynomial algorithm given 3-degenerate either finds 3-colouring exhibits subgraph (A some node at most three.)
springer.com
sci-hub.se 参考文章(13)
S. Fiorini, Edge-colourings of graphs ,(1977)
P. Erdös, On Some Aspects of my Work with Gabriel Dirac Annals of discrete mathematics. ,vol. 41, pp. 111- 116 ,(1988) , 10.1016/S0167-5060(08)70454-0
Horst Sachs, On colour critical graphs fundamentals of computation theory. pp. 390- 401 ,(1985) , 10.1007/BFB0028823
G. Koester, 4-critical 4-valent planar graphs constructed with crowns. MATHEMATICA SCANDINAVICA. ,vol. 67, pp. 15- 22 ,(1990) , 10.7146/MATH.SCAND.A-12316
D.A. Youngs, Gallai's problem on Dirac's construction Discrete Mathematics. ,vol. 101, pp. 343- 350 ,(1992) , 10.1016/0012-365X(92)90615-M
G. A. Dirac, A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs Journal of the London Mathematical Society. ,vol. s1-27, pp. 85- 92 ,(1952) , 10.1112/JLMS/S1-27.1.85
M.R. Garey, D.S. Johnson, L. Stockmeyer, Some simplified NP-complete graph problems Theoretical Computer Science. ,vol. 1, pp. 237- 267 ,(1976) , 10.1016/0304-3975(76)90059-1
E.C. Sewell, L.E. Trotter, Stability Critical Graphs and Even Subdivisions of K4 Journal of Combinatorial Theory, Series B. ,vol. 59, pp. 74- 84 ,(1993) , 10.1006/JCTB.1993.1055
Paul A Catlin, Hajós' graph-coloring conjecture: Variations and counterexamples Journal of Combinatorial Theory, Series B. ,vol. 26, pp. 268- 274 ,(1979) , 10.1016/0095-8956(79)90062-5
G. Koester, Note to a problem of T. Gallai and G. A. Dirac Combinatorica. ,vol. 5, pp. 227- 228 ,(1985) , 10.1007/BF02579365