Search

Greenberger-Horne-Zeilinger (GHZ) states are quantum states involving at least three entangled particles. They are of fundamental interest in quantum information theory, and the construction of such states of high dimension has various applications in quantum communication and cryptography. They are of fundamental interest in quantum information theory, and the construction of such states of high dimension has various applications in quantum communication and cryptography. Krenn, Gu and Zeilinger discovered a correspondence between a large class of quantum optical experiments which produce GHZ states and edge-weighted edge-coloured multi-graphs with some special properties called the \emph{GHZ graphs}. On such GHZ graphs, a graph parameter called \emph{dimension} can be defined, which is the same as the dimension of the GHZ state produced by the corresponding experiment. Krenn and Gu conjectured that the dimension of any GHZ graph with more than $4$ vertices is at most $2$. An affirmative resolution of the Krenn-Gu conjecture has implications for quantum resource theory. On the other hand, the construction of a GHZ graph on a large number of vertices with a high dimension would lead to breakthrough results. In this paper, we study the existence of GHZ graphs from the perspective of the Krenn-Gu conjecture and show that the conjecture is true for graphs of vertex connectivity at most 2 and for cubic graphs. We also show that the minimal counterexample to the conjecture should be $4$-connected. Such information could be of great help in the search for GHZ graphs using existing tools like PyTheus. While the impact of the work is in quantum physics, the techniques in this paper are purely combinatorial, and no background in quantum physics is required to understand them., Comment: To appear in MFCS 2024

A class of graphs $\mathcal{G}$ is $\chi$-bounded if there exists a function $f$ such that $\chi(G) \leq f(\omega(G))$ for each graph $G \in \mathcal{G}$, where $\chi(G)$ and $\omega(G)$ are the chromatic and clique number of $G$, respectively. The square of a graph $G$, denoted as $G^2$, is the graph with the same vertex set as $G$ in which two vertices are adjacent when they are at a distance at most two in $G$. In this paper, we study the $\chi$-boundedness of squares of bipartite graphs and its subclasses. Note that the class of squares of graphs, in general, admit a quadratic $\chi$-binding function. Moreover there exist bipartite graphs $B$ for which $\chi\left(B^2\right)$ is $\Omega\left(\frac{\left(\omega\left(B^2\right)\right)^2 }{\log \omega\left(B^2\right)}\right)$. We first ask the following question: "What sub-classes of bipartite graphs have a linear $\chi$-binding function?" We focus on the class of convex bipartite graphs and prove the following result: for any convex bipartite graph $G$, $\chi\left(G^2\right) \leq \frac{3 \omega\left(G^2\right)}{2}$. Our proof also yields a polynomial-time $3/2$-approximation algorithm for coloring squares of convex bipartite graphs. We then introduce a notion called "partite testable properties" for the squares of bipartite graphs. We say that a graph property $P$ is partite testable for the squares of bipartite graphs if for a bipartite graph $G=(A,B,E)$, whenever the induced subgraphs $G^2[A]$ and $G^2[B]$ satisfies the property $P$ then $G^2$ also satisfies the property $P$. Here, we discuss whether some of the well-known graph properties like perfectness, chordality, (anti-hole)-freeness, etc. are partite testable or not. As a consequence, we prove that the squares of biconvex bipartite graphs are perfect., Comment: 22 pages, 5 figures

A list assignment $L$ of a graph $G$ is a function that assigns to every vertex $v$ of $G$ a set $L(v)$ of colors. A proper coloring $\alpha$ of $G$ is called an $L$-coloring of $G$ if $\alpha(v)\in L(v)$ for every $v\in V(G)$. For a list assignment $L$ of $G$, the $L$-recoloring graph $\mathcal{G}(G,L)$ of $G$ is a graph whose vertices correspond to the $L$-colorings of $G$ and two vertices of $\mathcal{G}(G,L)$ are adjacent if their corresponding $L$-colorings differ at exactly one vertex of $G$. A $d$-face in a plane graph is a face of length $d$. Dvo\v{r}\'ak and Feghali conjectured for a planar graph $G$ and a list assignment $L$ of $G$, that: (i) If $|L(v)|\geq 10$ for every $v\in V(G)$, then the diameter of $\mathcal{G}(G,L)$ is $O(|V(G)|)$. (ii) If $G$ is triangle-free and $|L(v)|\geq 7$ for every $v\in V(G)$, then the diameter of $\mathcal{G}(G,L)$ is $O(|V(G)|)$. In a recent paper, Cranston (European J. Combin. (2022)) has proved (ii). In this paper, we prove the following results. Let $G$ be a plane graph and $L$ be a list assignment of $G$. $\bullet$ If for every $3$-face of $G$, there are at most two $3$-faces adjacent to it and $|L(v)|\geq 10$ for every $v\in V(G)$, then the diameter of $\mathcal{G}(G,L)$ is at most $190|V(G)|$. $\bullet$ If for every $3$-face of $G$, there is at most one $3$-face adjacent to it and $|L(v)|\geq 9$ for every $v\in V(G)$, then the diameter of $\mathcal{G}(G,L)$ is at most $13|V(G)|$. $\bullet$ If the faces adjacent to any $3$-face have length at least $6$ and $|L(v)|\geq 7$ for every $v\in V(G)$, then the diameter of $\mathcal{G}(G,L)$ is at most $242|V(G)|$. This result strengthens the Cranston's result on (ii).

Krenn, Gu and Zeilinger initiated the study of PMValid edge-colourings because of its connection to a problem from quantum physics. A graph is defined to have a PMValid $k$-edge-colouring if it admits a $k$-edge-colouring (i.e. an edge colouring with $k$-colours) with the property that all perfect matchings are monochromatic and each of the $k$ colour classes contain at least one perfect matching. The matching index of a graph $G$, $\mu(G)$ is defined as the maximum value of $k$ for which $G$ admits a PMValid $k$-edge-colouring. It is easy to see that $\mu(G)\geq 1$ if and only if $G$ has a perfect matching (due to the trivial $1$-edge-colouring which is PMValid). Bogdanov observed that for all graphs non-isomorphic to $K_4$, $\mu(G)\leq 2$ and $\mu(K_4)=3$. However, the characterisation of graphs for which $\mu(G)=1$ and $\mu(G)=2$ is not known. In this work, we answer this question. Using this characterisation, we also give a fast algorithm to compute $\mu(G)$ of a graph $G$. In view of our work, the structure of PMValid $k$-edge-colourable graphs is now fully understood for all $k$. Our characterisation, also has an implication to the aforementioned quantum physics problem. In particular, it settles a conjecture of Krenn and Gu for a sub-class of graphs., Comment: 18 pages and 7 figures

Given a finite family $\mathcal{F}$ of graphs, we say that a graph $G$ is "$\mathcal{F}$-free" if $G$ does not contain any graph in $\mathcal{F}$ as a subgraph. A vertex-colored graph $H$ is called "rainbow" if no two vertices of $H$ have the same color. Given an integer $s$ and a finite family of graphs $\mathcal{F}$, let $\ell(s,\mathcal{F})$ denote the smallest integer such that any properly vertex-colored $\mathcal{F}$-free graph $G$ having $\chi(G)\geq\ell(s,\mathcal{F})$ contains an induced rainbow path on $s$ vertices. Scott and Seymour showed that $\ell(s,K)$ exists for every complete graph $K$. A conjecture of N. R. Aravind states that $\ell(s,C_3)=s$. The upper bound on $\ell(s,C_3)$ that can be obtained using the methods of Scott and Seymour setting $K=C_3$ are, however, super-exponential. Gy\'arf\'as and S\'ark\"ozy showed that $\ell(s,\{C_3,C_4\})=\mathcal{O}\big((2s)^{2s}\big)$. For $r\geq 2$, we show that $\ell(s,K_{2,r})\leq (r-1)(s-1)(s-2)/2+s$ and therefore, $\ell(s,C_4)\leq\frac{s^2-s+2}{2}$. This significantly improves Gy\'arf\'as and S\'ark\"ozy's bound and also covers a bigger class of graphs. We adapt our proof to achieve much stronger upper bounds for graphs of higher girth: we prove that $\ell(s,\{C_3,C_4,\ldots,C_{g-1}\})\leq s^{1+\frac{4}{g-4}}$, where $g\geq 5$. Moreover, in each case, our results imply the existence of at least $s!/2$ distinct induced rainbow paths on $s$ vertices. Along the way, we obtain some results on related problems on oriented graphs. For $r\geq 2$, let $\mathcal{B}_r$ denote the orientations of $K_{2,r}$ in which one vertex has out-degree or in-degree $r$. We show that every $\mathcal{B}_r$-free oriented graph $G$ having $\chi(G)\geq (r-1)(s-1)(s-2)+2s+1$ and every bikernel-perfect oriented graph $G$ with girth $g\geq 5$ having $\chi(G)\geq 2s^{1+\frac{4}{g-4}}$ contains every $s$ vertex oriented tree as an induced subgraph., Comment: 21 pages, 1 figure

Hadwiger's conjecture is one of the most important and long-standing conjectures in graph theory. Reed and Seymour showed in 2004 that Hadwiger's conjecture is true for line graphs. We investigate this conjecture on the closely related class of total graphs. The total graph of $G$, denoted by $T(G)$, is defined on the vertex set $V(G)\sqcup E(G)$ with $c_1,c_2\in V(G)\sqcup E(G)$ adjacent whenever $c_1$ and $c_2$ are adjacent to or incident on each other in $G$. We first show that there exists a constant $C$ such that, if the connectivity of $G$ is at least $C$, then Hadwiger's conjecture is true for $T(G)$. The total chromatic number $\chi"(G)$ of a graph $G$ is defined to be equal to the chromatic number of its total graph. That is, $\chi"(G)=\chi(T(G))$. Another well-known conjecture in graph theory, the total coloring conjecture or TCC, states that for every graph $G$, $\chi"(G)\leq\Delta(G)+2$, where $\Delta(G)$ is the maximum degree of $G$. We show that if a weaker version of the total coloring conjecture (weak TCC) namely, $\chi"(G)\leq\Delta(G)+3$, is true for a class of graphs $\mathcal{F}$ that is closed under the operation of taking subgraphs, then Hadwiger's conjecture is true for the class of total graphs of graphs in $\mathcal{F}$. This motivated us to look for classes of graphs that satisfy weak TCC. It may be noted that a complete proof of TCC for even 4-colorable graphs (in fact even for planar graphs) has remained elusive even after decades of effort; but weak TCC can be proved easily for 4-colorable graphs. We noticed that in spite of the interest in studying $\chi"(G)$ in terms of $\chi(G)$ right from the initial days, weak TCC is not proven to be true for $k$-colorable graphs even for $k=5$. In the second half of the paper, we make a contribution to the literature on total coloring by proving that $\chi"(G)\leq\Delta(G)+3$ for every 5-colorable graph $G$.

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 $\text{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 $\text{rc}(G) \le |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 $\text{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\cdot t(G)$ is not an upper bound for $\text{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 $\text{rc}(G) \leq 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.

A code is called a $q$-query locally decodable code (LDC) if there is a randomized decoding algorithm that, given an index $i$ and a received word $w$ close to an encoding of a message $x$, outputs $x_i$ by querying only at most $q$ coordinates of $w$. Understanding the tradeoffs between the dimension, length and query complexity of LDCs is a fascinating and unresolved research challenge. In particular, for $3$-query binary LDCs of dimension $k$ and length $n$, the best known bounds are: $2^{k^{o(1)}} \geq n \geq \tilde{\Omega}(k^2)$. In this work, we take a second look at binary $3$-query LDCs. We investigate a class of 3-uniform hypergraphs that are equivalent to strong binary 3-query LDCs. We prove an upper bound on the number of edges in these hypergraphs, reproducing the known lower bound of $\tilde{\Omega}(k^2)$ for the length of strong $3$-query LDCs. In contrast to previous work, our techniques are purely combinatorial and do not rely on a direct reduction to $2$-query LDCs, opening up a potentially different approach to analyzing 3-query LDCs., Comment: 10 pages

The anti-Ramsey number $ar(G,H)$ with input graph $G$ and pattern graph $H$, is the maximum positive integer $k$ such that there exists an edge coloring of $G$ using $k$ colors, in which there are no rainbow subgraphs isomorphic to $H$ in $G$. ($H$ is rainbow if all its edges get distinct colors). The concept of anti-Ramsey number was introduced by Erd\"os, Simanovitz, and S\'os in 1973. Thereafter several researchers investigated this concept in the combinatorial setting. Recently, Feng et al. revisited the anti-Ramsey problem for the pattern graph $K_{1,t}$ (for $t \geq 3$) purely from an algorithmic point of view due to its applications in interference modeling of wireless networks. They posed it as an optimization problem, the maximum edge $q$-coloring problem. For a graph $G$ and an integer $q\geq 2$, an edge $q$-coloring of $G$ is an assignment of colors to edges of $G$, such that edges incident on a vertex span at most $q$ distinct colors. The maximum edge $q$-coloring problem seeks to maximize the number of colors in an edge $q$-coloring of the graph $G$. Note that the optimum value of the edge $q$-coloring problem of $G$ equals $ar(G,K_{1,q+1})$. In this paper, we study $ar(G,K_{1,t})$, the anti-Ramsey number of stars, for each fixed integer $t\geq 3$, both from combinatorial and algorithmic point of view. The first of our main results presents an upper bound for $ar(G,K_{1,q+1})$, in terms of number of vertices and the minimum degree of $G$. The second one improves this result for the case of triangle-free input graphs. For a positive integer $t$, let $H_t$ denote a subgraph of $G$ with maximum number of possible edges and maximum degree $t$. Our third main result presents an upper bound for $ar(G,K_{1,q+1})$ in terms of $|E(H_{q-1})|$. All our results have algorithmic consequences., Comment: 19 pages, 3 figures

It is well known that \textit{every} Eulerian orientation of an Eulerian $2k$-edge connected (undirected) graph is strongly $k$-edge connected. An important goal in the area is to obtain analogous results for other types of connectivity, such as node connectivity and element connectivity. We show that \textit{every} Eulerian orientation of the hypercube of degree $2k$ is strongly $k$-node connected.

A well-studied coloring problem is to assign colors to the edges of a graph $G$ so that, for every pair of vertices, all edges of at least one shortest path between them receive different colors. The minimum number of colors necessary in such a coloring is the strong rainbow connection number ($\src(G)$) of the graph. When proving upper bounds on $\src(G)$, it is natural to prove that a coloring exists where, for \emph{every} shortest path between every pair of vertices in the graph, all edges of the path receive different colors. Therefore, we introduce and formally define this more restricted edge coloring number, which we call \emph{very strong rainbow connection number} ($\vsrc(G)$). In this paper, we give upper bounds on $\vsrc(G)$ for several graph classes, some of which are tight. These immediately imply new upper bounds on $\src(G)$ for these classes, showing that the study of $\vsrc(G)$ enables meaningful progress on bounding $\src(G)$. Then we study the complexity of the problem to compute $\vsrc(G)$, particularly for graphs of bounded treewidth, and show this is an interesting problem in its own right. We prove that $\vsrc(G)$ can be computed in polynomial time on cactus graphs; in contrast, this question is still open for $\src(G)$. We also observe that deciding whether $\vsrc(G) = k$ is fixed-parameter tractable in $k$ and the treewidth of $G$. Finally, on general graphs, we prove that there is no polynomial-time algorithm to decide whether $\vsrc(G) \leq 3$ nor to approximate $\vsrc(G)$ within a factor $n^{1-\varepsilon}$, unless P$=$NP.

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-Vitaver Theorem that every properly coloured graph contains a colourful path on $\chi(G)$ vertices. We explore a conjecture that states that every properly coloured triangle-free graph $G$ contains an induced colourful path on $\chi(G)$ vertices and prove its correctness when the girth of $G$ is at least $\chi(G)$. Recent work on this conjecture by Gy\'arf\'as and S\'ark\"ozy, and Scott and Seymour has shown the existence of a function $f$ such that if $\chi(G)\geq f(k)$, then an induced colourful path on $k$ vertices is guaranteed to exist in any properly coloured triangle-free graph $G$., Comment: 8 pages, 3 figures

Hadwiger's conjecture asserts that any graph contains a clique minor with order no less than the chromatic number of the graph. We prove that this well-known conjecture is true for all graphs if and only if it is true for squares of split graphs. This observation implies that Hadwiger's conjecture for squares of chordal graphs is as difficult as the general case, since chordal graphs are a superclass of split graphs. Then we consider 2-trees which are a subclass of each of planar graphs, 2-degenerate graphs and chordal graphs. We prove that Hadwiger's conjecture is true for squares of $2$-trees. We achieve this by proving the following stronger result: for any $2$-tree $T$, its square $T^2$ has a clique minor of order $\chi(T^2)$ for which each branch set induces a path, where $\chi(T^2)$ is the chromatic number of $T^2$., Comment: 18 pages, 3 figures

The 'separation dimension' of a graph $G$ is the smallest natural number $k$ for which the vertices of $G$ can be embedded in $\mathbb{R}^k$ such that any pair of disjoint edges in $G$ can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family $\mathcal{F}$ of total orders of the vertices of $G$ such that for any two disjoint edges of $G$, there exists at least one total order in $\mathcal{F}$ in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on $n$ vertices is $\Theta(\log n)$. In this article, we focus on bounded degree graphs and show that the separation dimension of a graph with maximum degree $d$ is at most $2^{9log^{\star} d} d$. We also demonstrate that the above bound is nearly tight by showing that, for every $d$, almost all $d$-regular graphs have separation dimension at least $\lceil d/2\rceil$., Comment: One result proved in this paper is also present in arXiv:1212.6756

The boxicity (respectively cubicity) of a graph $G$ is the minimum non-negative integer $k$, such that $G$ can be represented as an intersection graph of axis-parallel $k$-dimensional boxes (respectively $k$-dimensional unit cubes) and is denoted by $box(G)$ (respectively $cub(G)$). It was shown by Adiga and Chandran (Journal of Graph Theory, 65(4), 2010) that for any graph $G$, $cub(G) \le$ box$(G) \left \lceil \log_2 \alpha \right \rceil$, where $\alpha = \alpha(G)$ is the cardinality of the maximum independent set in $G$. In this note we show that $cub(G) \le 2 \left \lceil \log_2 \chi(G) \right \rceil box(G) + \chi(G) \left \lceil \log_2 \alpha(G) \right \rceil $. In general, this result can provide a much better upper bound than that of Adiga and Chandran for graph classes with bounded chromatic number. For example, for bipartite graphs we get, $cub(G) \le 2 (box(G) + \left \lceil \log_2 \alpha(G) \right \rceil )$. Moreover we show that for every positive integer $k$, there exist graphs with chromatic number $k$, such that for every $\epsilon > 0$, the value given by our upper bound is at most $(1+\epsilon)$ times their cubicity. Thus, our upper bound is almost tight.

A family $\mathcal{F}$ of permutations of the vertices of a hypergraph $H$ is called 'pairwise suitable' for $H$ if, for every pair of disjoint edges in $H$, there exists a permutation in $\mathcal{F}$ in which all the vertices in one edge precede those in the other. The cardinality of a smallest such family of permutations for $H$ is called the 'separation dimension' of $H$ and is denoted by $\pi(H)$. Equivalently, $\pi(H)$ is the smallest natural number $k$ so that the vertices of $H$ can be embedded in $\mathbb{R}^k$ such that any two disjoint edges of $H$ can be separated by a hyperplane normal to one of the axes. We show that the separation dimension of a hypergraph $H$ is equal to the 'boxicity' of the line graph of $H$. This connection helps us in borrowing results and techniques from the extensive literature on boxicity to study the concept of separation dimension., Comment: This is the full version of a paper by the same name submitted to WG-2014. Some results proved in this paper are also present in arXiv:1212.6756. arXiv admin note: substantial text overlap with arXiv:1212.6756

The separation dimension of a graph $G$ is the smallest natural number $k$ for which the vertices of $G$ can be embedded in $\mathbb{R}^k$ such that any pair of disjoint edges in $G$ can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family $\mathcal{F}$ of permutations of the vertices of $G$ such that for any two disjoint edges of $G$, there exists at least one permutation in $\mathcal{F}$ in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on $n$ vertices is $\Theta(\log n)$. In this article, we focus on sparse graphs and show that the maximum separation dimension of a $k$-degenerate graph on $n$ vertices is $O(k \log\log n)$ and that there exists a family of $2$-degenerate graphs with separation dimension $\Omega(\log\log n)$. We also show that the separation dimension of the graph $G^{1/2}$ obtained by subdividing once every edge of another graph $G$ is at most $(1 + o(1)) \log\log \chi(G)$ where $\chi(G)$ is the chromatic number of the original graph., Comment: This is the full version of a paper to be presented at ICGT 2014. This is a subset of the results in arXiv:1212.6756

A rainbow path in an edge coloured graph is a path in which no two edges are coloured the same. A rainbow colouring of a connected graph G is a colouring of the edges of G such that every pair of vertices in G is connected by at least one rainbow path. The minimum number of colours required to rainbow colour G is called its rainbow connection number. Between them, Chakraborty et al. [J. Comb. Optim., 2011] and Ananth et al. [FSTTCS, 2012] have shown that for every integer k, k \geq 2, it is NP-complete to decide whether a given graph can be rainbow coloured using k colours. A split graph is a graph whose vertex set can be partitioned into a clique and an independent set. Chandran and Rajendraprasad have shown that the problem of deciding whether a given split graph G can be rainbow coloured using 3 colours is NP-complete and further have described a linear time algorithm to rainbow colour any split graph using at most one colour more than the optimum [COCOON, 2012]. In this article, we settle the computational complexity of the problem on split graphs and thereby discover an interesting dichotomy. Specifically, we show that the problem of deciding whether a given split graph can be rainbow coloured using k colours is NP-complete for k \in {2,3}, but can be solved in polynomial time for all other values of k., Comment: This is the full version of a paper to be presented at ICGT 2014. This complements the results in arXiv:1205.1670 (which were presented in COCOON 2013), and both will be merged into a single journal submission

Let $\mathbb{Z}_n$ denote the ring of integers modulo $n$. In this paper we consider two extremal problems on permutations of $\mathbb{Z}_n$, namely, the maximum size of a collection of permutations such that the sum of any two distinct permutations in the collection is again a permutation, and the maximum size of a collection of permutations such that the sum of any two distinct permutations in the collection is not a permutation. Let the sizes be denoted by $s(n)$ and $t(n)$ respectively. The case when $n$ is even is trivial in both the cases, with $s(n)=1$ and $t(n)=n!$. For $n$ odd, we prove $s(n)\geq (n\phi(n))/2^k$ where $k$ is the number of distinct prime divisors of $n$. When $n$ is an odd prime we prove $s(n)\leq \frac{e^2}{\pi} n ((n-1)/e)^\frac{n-1}{2}$. For the second problem, we prove $2^{(n-1)/2}.(\frac{n-1}{2})!\leq t(n)\leq 2^k.(n-1)!/\phi(n)$ when $n$ is odd., Comment: 9 pages

The 'boxicity' ('cubicity') of a graph G is the minimum natural number k such that G can be represented as an intersection graph of axis-parallel rectangular boxes (axis-parallel unit cubes) in $R^k$. In this article, we give estimates on the boxicity and the cubicity of Cartesian, strong and direct products of graphs in terms of invariants of the component graphs. In particular, we study the growth, as a function of $d$, of the boxicity and the cubicity of the $d$-th power of a graph with respect to the three products. Among others, we show a surprising result that the boxicity and the cubicity of the $d$-th Cartesian power of any given finite graph is in $O(\log d / \log\log d)$ and $\theta(d / \log d)$, respectively. On the other hand, we show that there cannot exist any sublinear bound on the growth of the boxicity of powers of a general graph with respect to strong and direct products., Comment: 14 pages

A family F of permutations of the vertices of a hypergraph H is called "pairwise suitable" for H if, for every pair of disjoint edges in H, there exists a permutation in F in which all the vertices in one edge precede those in the other. The cardinality of a smallest such family of permutations for H is called the "separation dimension" of H and is denoted by \pi(H). Equivalently, \pi(H) is the smallest natural number k so that the vertices of H can be embedded in R^k such that any two disjoint edges of H can be separated by a hyperplane normal to one of the axes. We show that the separation dimension of a hypergraph H is equal to the "boxicity" of the line graph of H. This connection helps us in borrowing results and techniques from the extensive literature on boxicity to study the concept of separation dimension., Comment: 28 pages

Given a connected outerplanar graph G of pathwidth p, we give an algorithm to add edges to G to get a supergraph of G, which is 2-vertex-connected, outerplanar and of pathwidth O(p). This settles an open problem raised by Biedl, in the context of computing minimum height planar straight line drawings of outerplanar graphs, with their vertices placed on a two dimensional grid. In conjunction with the result of this paper, the constant factor approximation algorithm for this problem obtained by Biedl for 2-vertex-connected outerplanar graphs will work for all outer planar graphs.

In this paper we demonstrate connections between three seemingly unrelated concepts. (1) The discrete isoperimetric problem in the infinite binary tree with all the leaves at the same level, $ {\mathcal T}_{\infty}$: The $n$-th edge isoperimetric number $\delta(n)$ is defined to be $\min_{|S|=n, S \subset V({\mathcal T}_{\infty})} |(S,\bar{S})|$, where $(S,\bar{S})$ is the set of edges in the cut defined by $S$. (2) Signed almost binary partitions: This is the special case of the coin-changing problem where the coins are drawn from the set ${\pm (2^d - 1): $d$ is a positive integer}$. The quantity of interest is $\tau(n)$, the minimum number of coins necessary to make change for $n$ cents. (3) Certain Meta-Fibonacci sequences: The Tanny sequence is defined by $T(n)=T(n{-}1{-}T(n{-}1))+T(n{-}2{-}T(n{-}2))$ and the Conolly sequence is defined by $C(n)=C(n{-}C(n{-}1))+C(n{-}1{-}C(n{-}2))$, where the initial conditions are $T(1) = C(1) = T(2) = C(2) = 1$. These are well-known "meta-Fibonacci" sequences. The main result that ties these three together is the following: $$ \delta(n) = \tau(n) = n+ 2 + 2 \min_{1 \le k \le n} (C(k) - T(n-k) - k).$$ Apart from this, we prove several other results which bring out the interconnections between the above three concepts., Comment: 22 pages, 4 figures

The product dimension of a graph G is defined as the minimum natural number l such that G is an induced subgraph of a direct product of l complete graphs. In this paper we study the product dimension of forests, bounded treewidth graphs and k-degenerate graphs. We show that every forest on n vertices has a product dimension at most 1.441logn+3. This improves the best known upper bound of 3logn for the same due to Poljak and Pultr. The technique used in arriving at the above bound is extended and combined with a result on existence of orthogonal Latin squares to show that every graph on n vertices with a treewidth at most t has a product dimension at most (t+2)(logn+1). We also show that every k-degenerate graph on n vertices has a product dimension at most \ceil{8.317klogn}+1. This improves the upper bound of 32klogn for the same by Eaton and Rodl., Comment: 12 pages, 3 figures

A rainbow colouring of a connected graph is a colouring of the edges of the graph, such that every pair of vertices is connected by at least one path in which no two edges are coloured the same. Such a colouring using minimum possible number of colours is called an optimal rainbow colouring, and the minimum number of colours required is called the rainbow connection number of the graph. In this article, we show the following: 1. The problem of deciding whether a graph can be rainbow coloured using 3 colours remains NP-complete even when restricted to the class of split graphs. However, any split graph can be rainbow coloured in linear time using at most one more colour than the optimum. 2. For every integer k larger than 2, the problem of deciding whether a graph can be rainbow coloured using k colours remains NP-complete even when restricted to the class of chordal graphs. 3. For every positive integer k, threshold graphs with rainbow connection number k can be characterised based on their degree sequence alone. Further, we can optimally rainbow colour a threshold graph in linear time., Comment: 15 pages, 3 figures, accepted for presentation at the 18th Annual International Computing and Combinatorics Conference (COCOON 2012)

Boxicity of a graph $G(V,$ $E)$, denoted by $box(G)$, is the minimum integer $k$ such that $G$ can be represented as the intersection graph of axis parallel boxes in $\mathbb{R}^k$. The problem of computing boxicity is inapproximable even for graph classes like bipartite, co-bipartite and split graphs within $O(n^{1 - \epsilon})$-factor, for any $\epsilon >0$ in polynomial time unless $NP=ZPP$. We give FPT approximation algorithms for computing the boxicity of graphs, where the parameter used is the vertex or edge edit distance of the given graph from families of graphs of bounded boxicity. This can be seen as a generalization of the parameterizations discussed in \cite{Adiga2}. Extending the same idea in one of our algorithms, we also get an $O\left(\frac{n\sqrt{\log \log n}}{\sqrt{\log n}}\right)$ factor approximation algorithm for computing boxicity and an $O\left(\frac{n {(\log \log n)}^{\frac{3}{2}}}{\sqrt{\log n}}\right)$ factor approximation algorithm for computing the cubicity. These seem to be the first $o(n)$ factor approximation algorithms known for both boxicity and cubicity. As a consequence of this result, a $o(n)$ factor approximation algorithm for computing the partial order dimension of finite posets and a $o(n)$ factor approximation algorithm for computing the threshold dimension of split graphs would follow.

We show that every graph of maximum degree 3 can be represented as the intersection graph of axis parallel boxes in three dimensions, that is, every vertex can be mapped to an axis parallel box such that two boxes intersect if and only if their corresponding vertices are adjacent. In fact, we construct a representation in which any two intersecting boxes just touch at their boundaries. Further, this construction can be realized in linear time.

Let k be an integer and k \geq 3. A graph G is k-chordal if G does not have an induced cycle of length greater than k. From the definition it is clear that 3-chordal graphs are precisely the class of chordal graphs. Duchet proved that, for every positive integer m, if G^m is chordal then so is G^{m+2}. Brandst\"adt et al. in [Andreas Brandst\"adt, Van Bang Le, and Thomas Szymczak. Duchet-type theorems for powers of HHD-free graphs. Discrete Mathematics, 177(1-3):9-16, 1997.] showed that if G^m is k-chordal, then so is G^{m+2}. Powering a bipartite graph does not preserve its bipartitedness. In order to preserve the bipartitedness of a bipartite graph while powering Chandran et al. introduced the notion of bipartite powering. This notion was introduced to aid their study of boxicity of chordal bipartite graphs. Given a bipartite graph G and an odd positive integer m, we define the graph G^{[m]} to be a bipartite graph with V(G^{[m]})=V(G) and E(G^{[m]})={(u,v) | u,v \in V(G), d_G(u,v) is odd, and d_G(u,v) \leq m}. The graph G^{[m]} is called the m-th bipartite power of G. In this paper we show that, given a bipartite graph G, if G is k-chordal then so is G^{[m]}, where k, m are positive integers such that k \geq 4 and m is odd., Comment: 10 pages

Rainbow connection number, $rc(G)$, of a connected graph $G$ is the minimum number of colours needed to colour its edges, so that every pair of vertices is connected by at least one path in which no two edges are coloured the same. In this paper we investigate the relationship of rainbow connection number with vertex and edge connectivity. It is already known that for a connected graph with minimum degree $\delta$, the rainbow connection number is upper bounded by $3n/(\delta + 1) + 3$ [Chandran et al., 2010]. This directly gives an upper bound of $3n/(\lambda + 1) + 3$ and $3n/(\kappa + 1) + 3$ for rainbow connection number where $\lambda$ and $\kappa$, respectively, denote the edge and vertex connectivity of the graph. We show that the above bound in terms of edge connectivity is tight up-to additive constants and show that the bound in terms of vertex connectivity can be improved to $(2 + \epsilon)n/\kappa + 23/ \epsilon^2$, for any $\epsilon > 0$. We conjecture that rainbow connection number is upper bounded by $n/\kappa + O(1)$ and show that it is true for $\kappa = 2$. We also show that the conjecture is true for chordal graphs and graphs of girth at least 7., Comment: 10 pages

A $k$-box $B=(R_1,...,R_k)$, where each $R_i$ is a closed interval on the real line, is defined to be the Cartesian product $R_1\times R_2\times ...\times R_k$. If each $R_i$ is a unit length interval, we call $B$ a $k$-cube. Boxicity of a graph $G$, denoted as $\boxi(G)$, is the minimum integer $k$ such that $G$ is an intersection graph of $k$-boxes. Similarly, the cubicity of $G$, denoted as $\cubi(G)$, is the minimum integer $k$ such that $G$ is an intersection graph of $k$-cubes. It was shown in [L. Sunil Chandran, Mathew C. Francis, and Naveen Sivadasan: Representing graphs as the intersection of axis-parallel cubes. MCDES-2008, IISc Centenary Conference, available at CoRR, abs/cs/ 0607092, 2006.] that, for a graph $G$ with maximum degree $\Delta$, $\cubi(G)\leq \lceil 4(\Delta +1)\log n\rceil$. In this paper, we show that, for a $k$-degenerate graph $G$, $\cubi(G) \leq (k+2) \lceil 2e \log n \rceil$. Since $k$ is at most $\Delta$ and can be much lower, this clearly is a stronger result. This bound is tight. We also give an efficient deterministic algorithm that runs in $O(n^2k)$ time to output a $8k(\lceil 2.42 \log n\rceil + 1)$ dimensional cube representation for $G$. An important consequence of the above result is that if the crossing number of a graph $G$ is $t$, then $\boxi(G)$ is $O(t^{1/4}{\lceil\log t\rceil}^{3/4})$ . This bound is tight up to a factor of $O((\log t)^{1/4})$. We also show that, if $G$ has $n$ vertices, then $\cubi(G)$ is $O(\log n + t^{1/4}\log t)$. Using our bound for the cubicity of $k$-degenerate graphs we show that cubicity of almost all graphs in $\mathcal{G}(n,m)$ model is $O(d_{av}\log n)$, where $d_{av}$ denotes the average degree of the graph under consideration., Comment: 21 pages

Rainbow connection number, rc(G), of a connected graph G is the minimum number of colors needed to color its edges so that every pair of vertices is connected by at least one path in which no two edges are colored the same (Note that the coloring need not be proper). In this paper we study the rainbow connection number with respect to three important graph product operations (namely cartesian product, lexicographic product and strong product) and the operation of taking the power of a graph. In this direction, we show that if G is a graph obtained by applying any of the operations mentioned above on non-trivial graphs, then rc(G) <= 2r(G)+c, where r(G) denotes the radius of G and c \in {0,1,2}. In general the rainbow connection number of a bridgeless graph can be as high as the square of its radius [Basavaraju et. al, 2010]. This is an attempt to identify some graph classes which have rainbow connection number very close to the obvious lower bound of diameter (and thus the radius). The bounds reported are tight upto additive constants. The proofs are constructive and hence yield polynomial time (2 + 2/r(G))-factor approximation algorithms., Comment: 15 pages. This is a revised (journal-ready) version

Boxicity of a graph $G(V,E)$ is the minimum integer $k$ such that $G$ can be represented as the intersection graph of $k$-dimensional axis parallel rectangles in $\mathbf{R}^k$. Equivalently, it is the minimum number of interval graphs on the vertex set $V$ such that the intersection of their edge sets is $E$. It is known that boxicity cannot be approximated even for graph classes like bipartite, co-bipartite and split graphs below $O(n^{0.5 - \epsilon})$-factor, for any $\epsilon >0$ in polynomial time unless $NP=ZPP$. Till date, there is no well known graph class of unbounded boxicity for which even an $n^\epsilon$-factor approximation algorithm for computing boxicity is known, for any $\epsilon <1$. In this paper, we study the boxicity problem on Circular Arc graphs - intersection graphs of arcs of a circle. We give a $(2+\frac{1}{k})$-factor polynomial time approximation algorithm for computing the boxicity of any circular arc graph along with a corresponding box representation, where $k \ge 1$ is its boxicity. For Normal Circular Arc(NCA) graphs, with an NCA model given, this can be improved to an additive 2-factor approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity is $O(mn+n^2)$ in both these cases and in $O(mn+kn^2)= O(n^3)$ time we also get their corresponding box representations, where $n$ is the number of vertices of the graph and $m$ is its number of edges. The additive 2-factor algorithm directly works for any Proper Circular Arc graph, since computing an NCA model for it can be done in polynomial time., Comment: 23 pages, 1 figure

The rainbow connection number, rc(G), of a connected graph G is the minimum number of colours needed to colour its edges, so that every pair of its vertices is connected by at least one path in which no two edges are coloured the same. In this note we show that for every bridgeless graph G with radius r, rc(G) <= r(r + 2). We demonstrate that this bound is the best possible for rc(G) as a function of r, not just for bridgeless graphs, but also for graphs of any stronger connectivity. It may be noted that for a general 1-connected graph G, rc(G) can be arbitrarily larger than its radius (Star graph for instance). We further show that for every bridgeless graph G with radius r and chordality (size of a largest induced cycle) k, rc(G) <= rk. It is known that computing rc(G) is NP-Hard [Chakraborty et al., 2009]. Here, we present a (r+3)-factor approximation algorithm which runs in O(nm) time and a (d+3)-factor approximation algorithm which runs in O(dm) time to rainbow colour any connected graph G on n vertices, with m edges, diameter d and radius r., Comment: Revised preprint with an extra section on an approximation algorithm. arXiv admin note: text overlap with arXiv:1101.5747

Rainbow connection number rc(G) of a connected graph G is the minimum number of colours needed to colour the edges of G, so that every pair of vertices is connected by at least one path in which no two edges are coloured the same. In this paper we show that for every connected graph G, with minimum degree at least 2, the rainbow connection number is upper bounded by {\gamma}_c(G) + 2, where {\gamma}_c(G) is the connected domination number of G. Bounds of the form diameter(G) \leq rc(G) \leq diameter(G) + c, 1 \leq c \leq 4, for many special graph classes follow as easy corollaries from this result. This includes interval graphs, AT-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) \leq 3.radius(G). In most of these cases, we also demonstrate the tightness of the bounds. An extension of this idea to two-step dominating sets is used to show that for every connected graph on n vertices with minimum degree {\delta}, the rainbow connection number is upper bounded by 3n/({\delta} + 1) + 3. This solves an open problem of Schiermeyer (2009), improving the previously best known bound of 20n/{\delta} by Krivelevich and Yuster (2010). Moreover, this bound is seen to be tight up to additive factors by a construction of Caro et al. (2008)., Comment: 14 pages

Boxicity of a graph H, denoted by box(H), is the minimum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in R^k. In this paper, we show that for a line graph G of a multigraph, box(G) <= 2\Delta(\lceil log_2(log_2(\Delta)) \rceil + 3) + 1, where \Delta denotes the maximum degree of G. Since \Delta <= 2(\chi - 1), for any line graph G with chromatic number \chi, box(G) = O(\chi log_2(log_2(\chi))). For the d-dimensional hypercube H_d, we prove that box(H_d) >= (\lceil log_2(log_2(d)) \rceil + 1)/2. The question of finding a non-trivial lower bound for box(H_d) was left open by Chandran and Sivadasan in [L. Sunil Chandran and Naveen Sivadasan. The cubicity of Hypercube Graphs. Discrete Mathematics, 308(23):5795-5800, 2008]. The above results are consequences of bounds that we obtain for the boxicity of fully subdivided graphs (a graph which can be obtained by subdividing every edge of a graph exactly once)., Comment: 14 pages

Let $G$ be a simple, undirected, finite graph with vertex set $V(G)$ and edge set $E(G)$. A $k$-dimensional box is a Cartesian product of closed intervals $[a_1,b_1]\times [a_2,b_2]\times...\times [a_k,b_k]$. The {\it boxicity} of $G$, $\boxi(G)$ is the minimum integer $k$ such that $G$ can be represented as the intersection graph of $k$-dimensional boxes, i.e. each vertex is mapped to a $k$-dimensional box and two vertices are adjacent in $G$ if and only if their corresponding boxes intersect. Let $\poset=(S,P)$ be a poset where $S$ is the ground set and $P$ is a reflexive, anti-symmetric and transitive binary relation on $S$. The dimension of $\poset$, $\dim(\poset)$ is the minimum integer $t$ such that $P$ can be expressed as the intersection of $t$ total orders. Let $G_\poset$ be the \emph{underlying comparability graph} of $\poset$, i.e. $S$ is the vertex set and two vertices are adjacent if and only if they are comparable in $\poset$. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset $\poset$, $\boxi(G_\poset)/(\chi(G_\poset)-1) \le \dim(\poset)\le 2\boxi(G_\poset)$, where $\chi(G_\poset)$ is the chromatic number of $G_\poset$ and $\chi(G_\poset)\ne1$. It immediately follows that if $\poset$ is a height-2 poset, then $\boxi(G_\poset)\le \dim(\poset)\le 2\boxi(G_\poset)$ since the underlying comparability graph of a height-2 poset is a bipartite graph. The second result of the paper relates the boxicity of a graph $G$ with a natural partial order associated with the \emph{extended double cover} of $G$, denoted as $G_c$: Note that $G_c$ is a bipartite graph with partite sets $A$ and $B$ which are copies of $V(G)$ such that corresponding to every $u\in V(G)$, there are two vertices $u_A\in A$ and $u_B\in B$ and $\{u_A,v_B\}$ is an edge in $G_c$ if and only if either $u=v$ or $u$ is adjacent to $v$ in $G$. Let $\poset_c$ be the natural height-2 poset associated with $G_c$ by making $A$ the set of minimal elements and $B$ the set of maximal elements. We show that $\frac{\boxi(G)}{2} \le \dim(\poset_c) \le 2\boxi(G)+4$. These results have some immediate and significant consequences. The upper bound $\dim(\poset)\le 2\boxi(G_\poset)$ allows us to derive hitherto unknown upper bounds for poset dimension such as $\dim(\poset)\le 2\tw(G_\poset)+4$, since boxicity of any graph is known to be at most its $\tw+2$. In the other direction, using the already known bounds for partial order dimension we get the following: (1) The boxicity of any graph with maximum degree $\Delta$ is $O(\Delta\log^2\Delta)$ which is an improvement over the best known upper bound of $\Delta^2+2$. (2) There exist graphs with boxicity $\Omega(\Delta\log\Delta)$. This disproves a conjecture that the boxicity of a graph is $O(\Delta)$. (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on $n$ vertices with a factor of $O(n^{0.5-\epsilon})$ for any $\epsilon>0$, unless $NP=ZPP$.

We study the $SIG$ dimension of trees under $L_{\infty}$ metric and answer an open problem posed by Michael and Quint (Discrete Applied Mathematics: 127, pages 447-460, 2003). Let $T$ be a tree with atleast two vertices. For each $v\in V(T)$, let leaf-degree$(v)$ denote the number of neighbours of $v$ that are leaves. We define the maximum leaf-degree as $\alpha(T) = \max_{x \in V(T)}$ leaf-degree$(x)$. Let $S = \{v\in V(T) |$ leaf-degree$(v) = \alpha\}$. If $|S| = 1$, we define $\beta(T) = \alpha(T) - 1$. Otherwise define $\beta(T) = \alpha(T)$. We show that for a tree $T$, $SIG_\infty(T) = \lceil \log_2(\beta + 2)\rceil$ where $\beta = \beta (T)$, provided $\beta$ is not of the form $2^k - 1$, for some positive integer $k \geq 1$. If $\beta = 2^k - 1$, then $SIG_\infty (T) \in \{k, k+1\}$. We show that both values are possible., Comment: 24 pages, 8 figures

The boxicity of a graph G is defined as the minimum integer k such that G is an intersection graph of axis-parallel k-dimensional boxes. Chordal bipartite graphs are bipartite graphs that do not contain an induced cycle of length greater than 4. It was conjectured by Otachi, Okamoto and Yamazaki that chordal bipartite graphs have boxicity at most 2. We disprove this conjecture by exhibiting an infinite family of chordal bipartite graphs that have unbounded boxicity., Comment: 9 pages, 1 figure

Let $G(V,E)$ be a simple, undirected graph where $V$ is the set of vertices and $E$ is the set of edges. A $b$-dimensional cube is a Cartesian product $I_1\times I_2\times...\times I_b$, where each $I_i$ is a closed interval of unit length on the real line. The \emph{cubicity} of $G$, denoted by $\cub(G)$ is the minimum positive integer $b$ such that the vertices in $G$ can be mapped to axis parallel $b$-dimensional cubes in such a way that two vertices are adjacent in $G$ if and only if their assigned cubes intersect. Suppose $S(m)$ denotes a star graph on $m+1$ nodes. We define \emph{claw number} $\psi(G)$ of the graph to be the largest positive integer $m$ such that $S(m)$ is an induced subgraph of $G$. It can be easily shown that the cubicity of any graph is at least $\ceil{\log_2\psi(G)}$. In this paper, we show that, for an interval graph $G$ $\ceil{\log_2\psi(G)}\le\cub(G)\le\ceil{\log_2\psi(G)}+2$. Till now we are unable to find any interval graph with $\cub(G)>\ceil{\log_2\psi(G)}$. We also show that, for an interval graph $G$, $\cub(G)\le\ceil{\log_2\alpha}$, where $\alpha$ is the independence number of $G$. Therefore, in the special case of $\psi(G)=\alpha$, $\cub(G)$ is exactly $\ceil{\log_2\alpha}$. The concept of cubicity can be generalized by considering boxes instead of cubes. A $b$-dimensional box is a Cartesian product $I_1\times I_2\times...\times I_b$, where each $I_i$ is a closed interval on the real line. The \emph{boxicity} of a graph, denoted $ box(G)$, is the minimum $k$ such that $G$ is the intersection graph of $k$-dimensional boxes. It is clear that $ box(G)\le\cub(G)$. From the above result, it follows that for any graph $G$, $\cub(G)\le box(G)\ceil{\log_2\alpha}$.

A $k$-dimensional box is the Cartesian product $R_1 \times R_2 \times ... \times R_k$ where each $R_i$ is a closed interval on the real line. The {\it boxicity} of a graph $G$, denoted as $\boxi(G)$, is the minimum integer $k$ such that $G$ can be represented as the intersection graph of a collection of $k$-dimensional boxes. A unit cube in $k$-dimensional space or a $k$-cube is defined as the Cartesian product $R_1 \times R_2 \times ... \times R_k$ where each $R_i$ is a closed interval on the real line of the form $[a_i,a_i + 1]$. The {\it cubicity} of $G$, denoted as $\cub(G)$, is the minimum integer $k$ such that $G$ can be represented as the intersection graph of a collection of $k$-cubes. The {\it threshold dimension} of a graph $G(V,E)$ is the smallest integer $k$ such that $E$ can be covered by $k$ threshold spanning subgraphs of $G$. In this paper we will show that there exists no polynomial-time algorithm to approximate the threshold dimension of a graph on $n$ vertices with a factor of $O(n^{0.5-\epsilon})$ for any $\epsilon >0$, unless $NP=ZPP$. From this result we will show that there exists no polynomial-time algorithm to approximate the boxicity and the cubicity of a graph on $n$ vertices with factor $O(n^{0.5-\epsilon})$ for any $ \epsilon >0$, unless $NP=ZPP$. 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 NP-complete to determine if a given split graph has boxicity at most 3., Comment: 13 pages

The boxicity of a graph G, denoted as box(G) is defined as the minimum integer t such that G is an intersection graph of axis-parallel t-dimensional boxes. A graph G is a k-leaf power if there exists a tree T such that the leaves of the tree correspond to the vertices of G and two vertices in G are adjacent if and only if their corresponding leaves in T are at a distance of at most k. Leaf powers are a subclass of strongly chordal graphs and are used in the construction of phylogenetic trees in evolutionary biology. We show that for a k-leaf power G, box(G)\leq k-1. We also show the tightness of this bound by constructing a k-leaf power with boxicity equal to k-1. This result implies that there exists strongly chordal graphs with arbitrarily high boxicity which is somewhat counterintuitive.

An axis parallel $d$-dimensional box is the Cartesian product $R_1 \times R_2 \times ... \times R_d$ where each $R_i$ is a closed interval on the real line. The {\it boxicity} of a graph $G$, denoted as $\boxi(G)$, is the minimum integer $d$ such that $G$ can be represented as the intersection graph of a collection of $d$-dimensional boxes. An axis parallel unit cube in $d$-dimensional space or a $d$-cube is defined as the Cartesian product $R_1 \times R_2 \times ... \times R_d$ where each $R_i$ is a closed interval on the real line of the form $[a_i,a_i + 1]$. The {\it cubicity} of $G$, denoted as $\cub(G)$, is the minimum integer $d$ such that $G$ can be represented as the intersection graph of a collection of $d$-cubes. Let $S(m)$ denote a star graph on $m+1$ nodes. We define {\it claw number} of a graph $G$ as the largest positive integer $k$ such that $S(k)$ is an induced subgraph of $G$ and denote it as $\claw$. Let $G$ be an AT-free graph with chromatic number $\chi(G)$ and claw number $\claw$. In this paper we will show that $\boxi(G) \leq \chi(G)$ and this bound is tight. We also show that $\cub(G) \leq \boxi(G)(\ceil{\log_2 \claw} +2)$ $\leq$ $\chi(G)(\ceil{\log_2 \claw} +2)$. If $G$ is an AT-free graph having girth at least 5 then $\boxi(G) \leq 2$ and therefore $\cub(G) \leq 2\ceil{\log_2 \claw} +4$., Comment: 15 pages: We are replacing our earlier paper regarding boxicity of permutation graphs with a superior result. Here we consider the boxicity of AT-free graphs, which is a super class of permutation graphs

A $k$-dimensional box is the cartesian product $R_1 \times R_2 \times ... \times R_k$ where each $R_i$ is a closed interval on the real line. The {\it boxicity} of a graph $G$, denoted as $box(G)$, is the minimum integer $k$ such that $G$ can be represented as the intersection graph of a collection of $k$-dimensional boxes: that is two vertices are adjacent if and only if their corresponding boxes intersect. A circular arc graph is a graph that can be represented as the intersection graph of arcs on a circle. Let $G$ be a circular arc graph with maximum degree $\Delta$. We show that if $\Delta <\lfloor \frac{n(\alpha-1)}{2\alpha}\rfloor$, $\alpha \in \mathbb{N}$, $\alpha \geq 2$ then $box(G) \leq \alpha$. We also demonstrate a graph with boxicity $> \alpha$ but with $\Delta=n\frac{(\alpha-1)}{2\alpha}+\frac{n}{2\alpha(\alpha+1)}+(\alpha+2)$. So the result cannot be improved substantially when $\alpha$ is large. Let $r_{inf}$ be minimum number of arcs passing through any point on the circle with respect to some circular arc representation of $G$. We also show that for any circular arc graph $G$, $box(G) \leq r_{inf} + 1$ and this bound is tight. Given a family of arcs $F$ on the circle, the circular cover number $L(F)$ is the cardinality of the smallest subset $F'$ of $F$ such that the arcs in $F'$ can cover the circle. Maximum circular cover number $L_{max}(G)$ is defined as the maximum value of $L(F)$ obtained over all possible family of arcs $F$ that can represent $G$. We will show that if $G$ is a circular arc graph with $L_{max}(G)> 4$ then $box(G) \leq 3$., Comment: 18 pages

An axis-parallel $b$-dimensional box is a Cartesian product $R_1\times R_2\times...\times R_b$ where $R_i$ is a closed interval of the form $[a_i,b_i]$ on the real line. For a graph $G$, its \emph{boxicity} box(G) is the minimum dimension $b$, such that $G$ is representable as the intersection graph of boxes in $b$-dimensional space. Although boxicity was introduced in 1969 and studied extensively, there are no significant results on lower bounds for boxicity. In this paper, we develop two general methods for deriving lower bounds. Applying these methods we give several results, some of which are listed below: (1) The boxicity of a graph on $n$ vertices with no universal vertices and minimum degree $\delta$ is at least $n/2(n-\delta-1)$. (2) Consider the $\mathcal{G}(n,p)$ model of random graphs. Let $ p \le 1- \frac{40 \log n}{n^2}$. Then, for $G \in \mathcal{G}(n,p)$, almost surely $box(G)=\Omega(np(1-p))$. On setting $p=1/2$ we immediately infer that almost all graphs have boxicity $\Omega(n)$. (3) Spectral lower bounds for the boxicity of $k$-regular graphs. (4) The boxicity of random $k$-regular graphs on $n$ vertices (where $k$ is fixed) is $\Omega(k/\log k)$. (5) There exists a positive constant$c$ such that almost all balanced bipartite graphs on $2n$ vertices with exactly $m$ edges have boxicity at least $c m/n$, for $ m\le c' n^2/3$ for any positive constant $c' < 1$., Comment: 20 pages

An $acyclic$ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The \emph{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)\le \Delta+2$, where $\Delta =\Delta(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 $\Delta+2$ colors to be acyclically edge colored. In this paper, using a simple counting argument we observe not only that this is not true, but infact all d-regular graphs with $2n$ vertices and $d > n$, requires at least $d+2$ colors. We also show that $a'(K_{n,n}) \ge n+2$, when $n$ is odd using a more non-trivial argument(Here $K_{n,n}$ denotes the complete bipartite graph with $n$ vertices on each side). This lower bound for $K_{n,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 \ge 5$, $n \ge 2d + 3$ and $dn$ even, there exist $d$-regular graphs which require at least $d+2$-colors to be acyclically edge colored., Comment: 4 pages

An $acyclic$ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycle s. The \emph{acyclic chromatic index} of a graph is the minimum number k such that there is an acyclic e dge coloring using k colors and is denoted by $a'(G)$. A graph is called 2-$degenerate$ if any of its induced subgraph has a vertex of degree at most 2. The class of 2-$degenerate graphs$ properly conta in $series$-$parallel graphs$, $outerplanar graphs$, \emph{non-regular subcubic graphs}, \emph{planar graphs of girth at least 6} and \emph{circle graphs of girth at least 5} as subclasses. It was conjectur ed by Alon, Sudakov and Zaks (and earlier by Fiamcik) that $a'(G)\le \Delta+2$, where $\Delta =\Delta(G)$ denotes the maximum deg ree of the graph. We prove the conjecture for 2-$degenerate$ graphs: in fact we prove a stronger bound . We prove that if $G$ is a 2-degenerate graph with maximum degree $\Delta$, then $a'(G)\le \Delta + 1$., Comment: 21 pages, 3 figures

An $acyclic$ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycle s. The \emph{acyclic chromatic index} of a graph is the minimum number k such that there is an acyclic e dge coloring using k colors and is denoted by $a'(G)$. It was conjectured by Alon, Sudakov and Zaks that for any simple and finite graph $G$, $a'(G)\le \Delta+2$, where $\Delta =\Delta(G)$ denotes the maximum degree of $G$. We prove the conjecture for connected graphs with $\Delta(G) \le 4$, with the additional restriction that $m \le 2n-1$, where $n$ is the number of vertices and $m$ is the number of edges in $G $. Note that for any graph $G$, $m \le 2n$, when $\Delta(G) \le 4$. It follows that for any graph $G$ if $\Delta(G) \le 4$, then $a'(G) \le 7$., Comment: 13 pages

A $k$-dimensional box is the cartesian product $R_1 \times R_2 \times ... \times R_k$ where each $R_i$ is a closed interval on the real line. The {\it boxicity} of a graph $G$, denoted as $box(G)$, is the minimum integer $k$ such that $G$ is the intersection graph of a collection of $k$-dimensional boxes. A unit cube in $k$-dimensional space or a $k$-cube is defined as the cartesian product $R_1 \times R_2 \times ... \times R_k$ where each $R_i$ is a closed interval on the real line of the form $[a_i, a_{i}+1]$. The {\it cubicity} of $G$, denoted as $cub(G)$, is the minimum $k$ such that $G$ is the intersection graph of a collection of $k$-cubes. In this paper we show that $cub(G) \leq t + \left \lceil \log (n - t)\right\rceil - 1$ and $box(G) \leq \left \lfloor\frac{t}{2}\right\rfloor + 1$, where $t$ is the cardinality of the minimum vertex cover of $G$ and $n$ is the number of vertices of $G$. 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 $G$, $box(G) \leq \left \lfloor\frac{n}{2} \right \rfloor$, where $n$ is the number of vertices of $G$, and this bound is tight. We show that if $G$ is a bipartite graph then $box(G) \leq \left \lceil\frac{n}{4} \right\rceil$ and this bound is tight. 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 $\frac{n}{4}$. Interestingly, if boxicity is very close to $\frac{n}{2}$, then chromatic number also has to be very high. In particular, we show that if $box(G) = \frac{n}{2} - s$, $s \geq 0$, then $\chi(G) \geq \frac{n}{2s+2}$, where $\chi(G)$ is the chromatic number of $G$., Comment: 12 pages

A k-dimensional box is the Cartesian product R_1 x R_2 x ... x R_k where each R_i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G) is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. Halin graphs are the graphs formed by taking a tree with no degree 2 vertex and then connecting its leaves to form a cycle in such a way that the graph has a planar embedding. We prove that if G is a Halin graph that is not isomorphic to K_4, then box(G)=2. In fact, we prove the stronger result that if G is a planar graph formed by connecting the leaves of any tree in a simple cycle, then box(G)=2 unless G is isomorphic to K_4 (in which case its boxicity is 1)., Comment: 9 pages

Let G = (V,E) be a finite, simple and undirected graph. For $S \subseteq V$, let $\delta(S,G) = \{(u,v) \in E : u \in S \mbox {and} v \in V-S \}$ be the edge boundary of $S$. Given an integer $i$, $1 \leq i \leq | V |$, let the edge isoperimetric value of $G$ at $i$ be defined as $b_e(i,G) = \min_{S \subseteq V; |S| = i} |\delta(S,G)|$. The edge isoperimetric peak of $G$ is defined as $b_e(G)=\max_{1 \leq j \leq | V |} b_e(j,G)$. Let $b_v(G)$ denote the vertex isoperimetric peak defined in a corresponding way. The problem of determining a lower bound for the vertex isoperimetric peak in complete $t$-ary trees was recently considered in \cite{OatYam}. In this paper we provide bounds which improve those in \cite{OatYam}. We show that for a complete binary tree of depth $d$ (denoted as $T_d^2$), $c_1d \leq b_e(T_d^2) \leq d$ and $c_2d \leq b_v(T_d^2) \leq d$ where $c_1$, $c_2$ are constants. For a complete $t$-ary tree of depth $d$ (denoted as $T_d^t$) and $d \geq c\log{t}$ where $c$ is a constant, we show that $c_1\sqrt{t}d \leq b_e(T_d^t) \leq td$ and $c_2\frac{d}{\sqrt{t}} \leq b_v(T_d^t) \leq d$ where $c_1$, $c_2$ are constants. Our results are generalized to arbitrary(rooted) trees., Comment: 18 pages