Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài:Coloring with no 2-colored P4’s. | Coloring with no 2-colored P4 s Michael O. Albertson Department of Mathematics Smith College Northhampton MA 01063 albertson@ Glenn G. Chappell Department of Mathematical Sciences University of Alaska Fairbanks Fairbanks AK 99775-6660 chappellg@ H. A. Kierstead Department of Mathematics and Statistics Arizona State University Tempe AZ 85287-1804 kierstead@ Andre Kiindgen Department of Mathematics California State University San Marcos San Marcos CA 92096-0001 akundgen@ Radhika Ramamurthi Department of Mathematics California State University San Marcos San Marcos CA 92096-0001 ramamurt@ March 25 2004 Submitted Sep 2 2002 Accepted Feb 2 2004 Published Mar 31 2004 MR Subject Classifications 05C15 Abstract A proper coloring of the vertices of a graph is called a star coloring if every two color classes induce a star forest. Star colorings are a strengthening of acyclic colorings . proper colorings in which every two color classes induce a forest. We show that every acyclic fc-coloring can be refined to a star coloring with at most 2fc2 fc colors. Similarly we prove that planar graphs have star colorings with at most 20 colors and we exhibit a planar graph which requires 10 colors. We prove several other structural and topological results for star colorings such as cubic graphs are 7-colorable and planar graphs of girth at least 7 are 9-colorable. We provide a short proof of the result of Fertin Raspaud and Reed that graphs with tree-width t can be star colored with g2 colors and we show that this is best possible. THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R26 1 1 Introduction A proper r-coloring of a graph G is an assignment of labels from 1 2 . r to the vertices of G so that adjacent vertices receive distinct labels. The minimum r so that G has a proper r-coloring is called the chromatic number of G denoted by x G . The chromatic number is one of the most studied parameters in graph theory and by convention the
