کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430559 | 688041 | 2013 | 12 صفحه PDF | دانلود رایگان |
An acyclic k-coloring of a graph G is a mapping ϕ from the set of vertices of G to a set of k distinct colors such that no two adjacent vertices receive the same color and ϕ does not contain any bichromatic cycle. In this paper we prove that every planar graph with n vertices has a 1-subdivision that is acyclically 3-colorable (respectively, 4-colorable), where the number of division vertices is at most 2n−52n−5 (respectively, n−3n−3). On the other hand, we prove a 1.28n (respectively, 0.3n) lower bound on the number of division vertices for acyclic 3-colorings (respectively, 4-colorings) of planar graphs. Furthermore, we establish the NP-completeness of deciding acyclic 4-colorability for graphs with maximum degree 5 and for planar graphs with maximum degree 7.
Journal: Journal of Discrete Algorithms - Volume 23, November 2013, Pages 42–53