Note on a conjecture of toft |
| |
Authors: | T. R. Jensen F. B. Shepherd |
| |
Affiliation: | (1) Department of Mathematics and Computer Science, Odense University, Odense, Denmark;(2) Mathematics and Operational Research, London School of Economics, London, U.K. |
| |
Abstract: | 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 that if a graphG has a degree three nodev such thatG-v is 3-colourable, then eitherG is 3-colourable or it contains a fully oddK4. This resolves Toft's conjecture in the special case where a 4-critical graph has a degree three node, which is in turn used to prove the conjecture for line-graphs. The proof is constructive and yields a polynomial algorithm which given a 3-degenerate graph either finds a 3-colouring or exhibits a subgraph that is a fully odd subdivision ofK4. (A graph is 3-degenerate if every subgraph has some node of degree at most three.) |
| |
Keywords: | 05 C 15 05 C 38 05 C 85 |
本文献已被 SpringerLink 等数据库收录! |
|