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]

The rainbow connection number of a connected graph is the minimum number of colors needed to color its edges, so that every pair of its vertices is connected by at least one path in which no two edges are colored the same. In this article we show that for every connected graph on n vertices with minimum degree δ, the rainbow connection number is upper bounded by 3 n/(δ + 1) + 3. This solves an open problem from Schiermeyer (Combinatorial Algorithms, Springer, Berlin/Hiedelberg, 2009, pp. 432-437), improving the previously best known bound of 20 n/δ (J Graph Theory 63 (2010), 185-191). This bound is tight up to additive factors by a construction mentioned in Caro et al. (Electr J Combin 15(R57) (2008), 1). As an intermediate step we obtain an upper bound of 3 n/(δ + 1) − 2 on the size of a connected two-step dominating set in a connected graph of order n and minimum degree δ. This bound is tight up to an additive constant of 2. This result may be of independent interest. We also show that for every connected graph G with minimum degree at least 2, the rainbow connection number, rc( G), is upper bounded by Γ c( G) + 2, where Γ c( G) is the connected domination number of G. Bounds of the form diameter( G)⩽ rc( G)⩽ diameter( G) + c, 1⩽ c⩽4, for many special graph classes follow as easy corollaries from this result. This includes interval graphs, asteroidal triple-free graphs, circular arc graphs, threshold graphs, and chain graphs all with minimum degree at least 2 and connected. We also show that every bridge-less chordal graph G has rc( G)⩽3· radius( G). In most of these cases, we also demonstrate the tightness of the bounds. [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 d-dimensional box is a Cartesian product of d closed intervals on the real line. The boxicity of a graph is the minimum dimension d such that it is representable as the intersection graph of d-dimensional boxes. We give a short constructive proof that every graph with maximum degree D has boxicity at most . We also conjecture that the best upper bound is linear in D. [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]