Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
438058 | Theoretical Computer Science | 2008 | 8 Pages |
Abstract
A graph G is equitably k-choosable if, for any k-uniform list assignment L, G is L-colorable and each color appears on at most vertices. A graph G is equitably k-colorable if G has a proper k-vertex coloring such that the sizes of any two color classes differ by at most 1. In this paper, we prove that every planar graph G is equitably k-choosable and equitably k-colorable if one of the following conditions holds: (1) G is triangle-free and k≥max{Δ(G),8}; (2) G has no 4- and 5-cycles and k≥max{Δ(G),7}.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics