Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4657439 | Journal of Combinatorial Theory, Series B | 2007 | 16 Pages |
Abstract
Grötzsch proved that every planar triangle-free graph is 3-colorable. We prove that it has at least distinct 3-colorings where n is the number of vertices. If the graph has girth at least 5, then it has at least distinct list-colorings provided every vertex has at least three available colors.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics