Search

Given a graph G = ( V , E ) whose vertices have been properly coloured, we say that a path in G is colourful if no two vertices in the path have the same colour. It is a corollary of the Gallai-Roy Theorem that every properly coloured graph contains a colourful path on χ ( G ) vertices. We explore a conjecture that states that every properly coloured triangle-free graph G contains an induced colourful path on χ ( G ) vertices and prove its correctness when the girth of G is at least χ ( G ) . Recent work on this conjecture by Gyárfás and Sárközy, and Scott and Seymour has shown the existence of a function f such that if χ ( G ) ≥ f ( k ) , then an induced colourful path on k vertices is guaranteed to exist in any properly coloured triangle-free graph G . [ABSTRACT FROM AUTHOR]

Abstract: An axis-parallel -dimensional box is a Cartesian product where each (for ) is a closed interval of the form on the real line. The boxicity of any graph , is the minimum positive integer such that G can be represented as the intersection graph of axis-parallel -dimensional boxes. A -dimensional cube is a Cartesian product , where each (for ) is a closed interval of the form on the real line. When the boxes are restricted to be axis-parallel cubes in -dimension, the minimum dimension required to represent the graph is called the cubicity of the graph (denoted by ). In this paper we prove that , where is the number of vertices in the graph. We also show that this upper bound is tight. Some immediate consequences of the above result are listed below: [1.] Planar graphs have cubicity at most . [2.] Outer planar graphs have cubicity at most . [3.] Any graph of treewidth has cubicity at most . Thus, chordal graphs have cubicity at most and circular arc graphs have cubicity at most , where is the clique number. The above upper bounds are tight, but for small constant factors. [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: The notion of the carvingwidth of a graph was introduced by Seymour and Thomas [Call routing and the ratcatcher, Combinatorica 14 (1994) 217–241]. In this note, we show that the carvingwidth of a d-dimensional hypercube equals . [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]

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 can be represented as 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 integer such that can be represented as the intersection graph of a collection of -cubes. The threshold dimension of a graph is the smallest integer such that can be covered by threshold spanning subgraphs of . In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on vertices with a factor of for any unless . From this result we will show that there exists no polynomial-time algorithm for approximating the boxicity and the cubicity of a graph on vertices with factor for any unless . In fact all these hardness results hold even for a highly structured class of graphs, namely the split graphs. We will also show that it is -complete to determine whether a given split graph has boxicity at most 3. [ABSTRACT FROM AUTHOR]