Search

A path in an edge-colored graph is rainbow if no two edges of it are colored the same, and the graph is rainbow-connected if there is a rainbow path between each pair of its vertices. The minimum number of colors needed to rainbow-connect a graph G is the rainbow connection number of G , denoted by rc (G). A simple way to rainbow-connect a graph G is to color the edges of a spanning tree with distinct colors and then re-use any of these colors to color the remaining edges of G. This proves that rc (G) ≤ | V (G) | − 1. We ask whether there is a stronger connection between tree-like structures and rainbow coloring than that is implied by the above trivial argument. For instance, is it possible to find an upper bound of t (G) − 1 for rc (G) , where t (G) is the number of vertices in the largest induced tree of G ? The answer turns out to be negative, as there are counter-examples that show that even c ⋅ t (G) is not an upper bound for rc (G) for any given constant c. In this work we show that if we consider the forest number f (G) , the number of vertices in a maximum induced forest of G , instead of t (G) , then surprisingly we do get an upper bound. More specifically, we prove that rc (G) ≤ f (G) + 2. Our result indicates a stronger connection between rainbow connection and tree-like structures than that was suggested by the simple spanning tree based upper bound. [ABSTRACT FROM AUTHOR]

Abstract: A -dimensional box is the cartesian product where each is a closed interval on the real line. The boxicity of a graph , denoted as , is the minimum integer such that is the intersection graph of a collection of -dimensional boxes. A unit cube in -dimensional space or a -cube is defined as the cartesian product where each is a closed interval on the real line of the form . The cubicity of , denoted as , is the minimum such that is the intersection graph of a collection of -cubes. In this paper we show that and , where is the cardinality of a minimum vertex cover of and is the number of vertices of . We also show the tightness of these upper bounds. F.S. Roberts in his pioneering paper on boxicity and cubicity had shown that for a graph , and , where is the number of vertices of , and these bounds are tight. We show that if is a bipartite graph then and this bound is tight. We also show that if is a bipartite graph then . We point out that there exist graphs of very high boxicity but with very low chromatic number. For example there exist bipartite (i.e., 2 colorable) graphs with boxicity equal to . Interestingly, if boxicity is very close to , then chromatic number also has to be very high. In particular, we show that if , , then , where is the chromatic number of . [Copyright &y& Elsevier]

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 such that there is an acyclic edge coloring using colors and it is denoted by . From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors. [Copyright &y& Elsevier]

Abstract: An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic (2-) cycles. The acyclic chromatic index of a graph is the minimum number such that there is an acyclic edge coloring using colors and is denoted by . Let denote the maximum degree of a vertex in a graph . A complete bipartite graph with vertices on each side is denoted by . Alon, McDiarmid and Reed observed that for every prime . In this paper we prove that when is prime. Basavaraju, Chandran and Kummini proved that when is odd, which combined with our result implies that when is an odd prime. Moreover we show that if we remove any edge from , the resulting graph is acyclically -edge-colorable. [Copyright &y& Elsevier]