K Colors (k + color)

Distribution by Scientific Domains


Selected Abstracts


Multi-coloring the Mycielskian of graphs

JOURNAL OF GRAPH THEORY, Issue 4 2010
Wensong Lin
Abstract A k -fold coloring of a graph is a function that assigns to each vertex a set of k colors, so that the color sets assigned to adjacent vertices are disjoint. The kth chromatic number of a graph G, denoted by ,k(G), is the minimum total number of colors used in a k -fold coloring of G. Let (G) denote the Mycielskian of G. For any positive integer k, it holds that ,k(G) + 1,,k((G)),,k(G) + k (W. Lin, Disc. Math., 308 (2008), 3565,3573). Although both bounds are attainable, it was proved in (Z. Pan, X. Zhu, Multiple coloring of cone graphs, manuscript, 2006) that if k,2 and ,k(G),3k,2, then the upper bound can be reduced by 1, i.e., ,k((G)),,k(G) + k,1. We conjecture that for any n,3k,1, there is a graph G with ,k(G)=n and ,k((G))=n+ k. This is equivalent to conjecturing that the equality ,k((K(n, k)))=n+k holds for Kneser graphs K(n, k) with n,3k,1. We confirm this conjecture for k=2, 3, or when n is a multiple of k or n,3k2/ln k. Moreover, we determine the values of ,k((C2q+1)) for 1,k,q. 2009 Wiley Periodicals, Inc. J Graph Theory 63: 311,323, 2010 [source]


d -Regular graphs of acyclic chromatic index at least d+2

JOURNAL OF GRAPH THEORY, Issue 3 2010
Manu Basavaraju
Abstract An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a,(G). It was conjectured by Alon, Sudakov and Zaks (and earlier by Fiamcik) that a,(G),,+2, where ,=,(G) denotes the maximum degree of the graph. Alon et al. also raised the question whether the complete graphs of even order are the only regular graphs which require ,+2 colors to be acyclically edge colored. In this article, using a simple counting argument we observe not only that this is not true, but in fact all d -regular graphs with 2n vertices and d>n, requires at least d+ 2 colors. We also show that a,(Kn, n),n+ 2, when n is odd using a more non-trivial argument. (Here Kn, n denotes the complete bipartite graph with n vertices on each side.) This lower bound for Kn, n can be shown to be tight for some families of complete bipartite graphs and for small values of n. We also infer that for every d, n such that d,5, n,2d+ 3 and dn even, there exist d -regular graphs which require at least d+2-colors to be acyclically edge colored. 2009 Wiley Periodicals, Inc. J Graph Theory 63: 226,230, 2010 [source]


Multicolored trees in complete graphs

JOURNAL OF GRAPH THEORY, Issue 3 2007
S. Akbari
Abstract A multicolored tree is a tree whose edges have different colors. Brualdi and Hollingsworth 5 proved in any proper edge coloring of the complete graph K2n(n > 2) with 2n , 1 colors, there are two edge-disjoint multicolored spanning trees. In this paper we generalize this result showing that if (a1,,, ak) is a color distribution for the complete graph Kn, n,,,5, such that , then there exist two edge-disjoint multicolored spanning trees. Moreover, we prove that for any edge coloring of the complete graph Kn with the above distribution if T is a non-star multicolored spanning tree of Kn, then there exists a multicolored spanning tree T' of Kn such that T and T' are edge-disjoint. Also it is shown that if Kn, n , 6, is edge colored with k colors and , then there exist two edge-disjoint multicolored spanning trees. 2006 Wiley Periodicals, Inc. J Graph Theory 54: 221,232, 2007 [source]


The game chromatic number of random graphs

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2008
Tom Bohman
Given a graph G and an integer k, two players take turns coloring the vertices of G one by one using k colors so that neighboring vertices get different colors. The first player wins iff at the end of the game all the vertices of G are colored. The game chromatic number ,g(G) is the minimum k for which the first player has a winning strategy. In this study, we analyze the asymptotic behavior of this parameter for a random graph Gn,p. We show that with high probability, the game chromatic number of Gn,p is at least twice its chromatic number but, up to a multiplicative constant, has the same order of magnitude. We also study the game chromatic number of random bipartite graphs. 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008 [source]