Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Colorful Paths in Vertex Coloring of Graphs. | Colorful Paths in Vertex Coloring of Graphs Saieed Akbari Department of Mathematical Sciences Sharif University of Technology Tehran Iran School of Mathematics Institute for Research in Fundamental Sciences IPM Tehran Iran s_akbari@ Vahid Liaghat Afshin Nikzad Computer Engineering Department Sharif University of Technology Tehran Iran liaghat@ Computer Engineering Department Sharif University of Technology Tehran Iran nikzad@ Submitted Nov 16 2009 Accepted Dec 22 2010 Published Jan 12 2011 Mathematics Subject Classification 05C15 Abstract A colorful path in a graph G is a path with x G vertices whose colors are different. A v-colorful path is such a path starting from v. Let G C7 be a connected graph with maximum degree A G . We show that there exists a A G 1 -coloring of G with a v-colorful path for every v E V G . We also prove that this result is true if one replaces A G 1 colors with 2x G colors. If x G w G then the result still holds for x G colors. For every graph G we show that there exists a x G -coloring of G with a rainbow path of length _x G 2j starting from each v E V G . Keywords Vertex-coloring Colorful path Rainbow path 1 Introduction Throughout this paper all graphs are simple. Let G be a graph and V G be the vertex set of G. In a connected graph G for any two vertices u v E V G let dG u v denote the Corresponding author. S. Akbari THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P17 1 length of the shortest path between u and v in G. We denote the DFS tree in G rooted at v by T G v which is defined in 2 . For every u G V G each vertex on the path between u and v in T G v is called an ancestor of u. By Theorem of 2 in every DFS tree if w and w are adjacent then one of them is ancestor of another. In a graph G a k-coloring of G is a function c V G 0 . k 1 such that c u c v for every adjacent vertices u v G V G . The chromatic number of G denoted by x G is the smallest k for which G has a k-coloring. For .
