Proof of Toft's Conjecture: Every Graph Containing No Fully Odd K4 is 3-Colorable |
| |
| Authors: | Wenan Zang |
| |
| Institution: | (1) Department of Mathematics, University of Hong Kong, Hong Kong |
| |
| Abstract: | A fully odd K4 is a subdivision of K4 such that each of the six edges of the K4 is subdivided into a path of odd length. In 1974, Toft conjectured that every graph containing no fully odd K4 can be vertex-colored with three colors. The purpose of this paper is to prove Toft's conjecture. |
| |
| Keywords: | graph coloring chromatic number minor subdivision polynomial time algorithm |
| 本文献已被 SpringerLink 等数据库收录！ |
