BZPEER

preprint2023arXiv

New bounds on the anti-Ramsey numbers of star graphs

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ös, Simanovitz, and Sós 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.

preprint2022arXiv

Weakening Total Coloring Conjecture: Weak TCC and Hadwiger's Conjecture on Total Graphs

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 $χ"(G)$ of a graph $G$ is defined to be equal to the chromatic number of its total graph. That is, $χ"(G)=χ(T(G))$ . Another well-known conjecture in graph theory, the total coloring conjecture or TCC, states that for every graph $G$ , $χ"(G)\leqΔ(G)+2$ , where $Δ(G)$ is the maximum degree of $G$ . We show that if a weaker version of the total coloring conjecture (weak TCC) namely, $χ"(G)\leqΔ(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 $χ"(G)$ in terms of $χ(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 $χ"(G)\leqΔ(G)+3$ for every 5-colorable graph $G$ .

preprint2020arXiv

Upper Bounding Rainbow Connection Number by Forest Number

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.

preprint2015arXiv

Sublinear Approximation Algorithms for Boxicity and Related Problems

Boxicity of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes in $\mathbb{R}^k$ . Cubicity is a variant of boxicity, where the axis parallel boxes in the intersection representation are restricted to be of unit length sides. Deciding whether boxicity (resp. cubicity) of a graph is at most k is NP-hard, even for k=2 or 3. Computing these parameters is inapproximable within $O(n^{1 - ε})$ -factor, for any $ε>0$ in polynomial time unless NP=ZPP, even for many simple graph classes. In this paper, we give a polynomial time $κ(n)$ factor approximation algorithm for computing boxicity and a $κ(n)\lceil \log \log n\rceil$ factor approximation algorithm for computing the cubicity, where $κ(n) =2\left\lceil\frac{n\sqrt{\log \log n}}{\sqrt{\log n}}\right\rceil$ . These o(n) factor approximation algorithms also produce the corresponding box (resp. cube) representations. As a special case, this resolves the question paused by Spinrad about polynomial time construction of o(n) dimensional box representations for boxicity 2 graphs. Other consequences of our approximation algorithm include $O(κ(n))$ factor approximation algorithms for computing the following parameters: the partial order dimension of finite posets, the interval dimension of finite posets, minimum chain cover of bipartite graphs, threshold dimension of split graphs and Ferrer's dimension of digraphs. Each of these parameters is inapproximable within an $O(n^{1 - ε})$ -factor, for any $ε>0$ in polynomial time unless NP=ZPP and the algorithms we derive seem to be the first o(n) factor approximation algorithms known for all these problems.

preprint2014arXiv

2-connecting Outerplanar Graphs without Blowing Up the Pathwidth

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.

preprint2014arXiv

Boxicity and separation dimension

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 $π(H)$ . Equivalently, $π(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.

preprint2014arXiv

On Additive Combinatorics of Permutations of \mathbb{Z}_n

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ϕ(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}π 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)!/ϕ(n)$ when $n$ is odd.

preprint2014arXiv

Parameterized and Approximation Algorithms for Boxicity

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 - ε})$ -factor, for any $ε>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.

preprint2014arXiv

Rainbow Colouring of Split Graphs

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.

preprint2014arXiv

Separation dimension of bounded degree graphs

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 $Θ(\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$ .

preprint2014arXiv

Separation dimension of sparse graphs

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 $Θ(\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 $Ω(\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 χ(G)$ where $χ(G)$ is the chromatic number of the original graph.

preprint2014arXiv

Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

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 α\right \rceil$ , where $α= α(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 χ(G) \right \rceil box(G) + χ(G) \left \lceil \log_2 α(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 α(G) \right \rceil )$ . Moreover we show that for every positive integer $k$ , there exist graphs with chromatic number $k$ , such that for every $ε> 0$ , the value given by our upper bound is at most $(1+ε)$ times their cubicity. Thus, our upper bound is almost tight.

preprint2013arXiv

Boxicity and Cubicity of Product Graphs

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 $θ(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.

preprint2012arXiv

Bipartite powers of k-chordal graphs

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ädt et al. in [Andreas Brandstädt, 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.

preprint2012arXiv

Cubicity, Degeneracy, and Crossing Number

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 $Δ$ , $\cubi(G)\leq \lceil 4(Δ+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 $Δ$ 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.

preprint2012arXiv

Isoperimetric Sequences for Infinite Complete Binary Trees, Meta-Fibonacci Sequences and Signed Almost Binary Partitions

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 $δ(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 $τ(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: $δ(n) = τ(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.

preprint2012arXiv

Lower Bounds for Boxicity

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 $δ$ is at least $n/2(n-δ-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)=Ω(np(1-p))$ . On setting $p=1/2$ we immediately infer that almost all graphs have boxicity $Ω(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 $Ω(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$ .

preprint2012arXiv

Pairwise Suitable Family of Permutations and Boxicity

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 π(H). Equivalently, π(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.

preprint2012arXiv

Product Dimension of Forests and Bounded Treewidth Graphs

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.

preprint2012arXiv

Rainbow Colouring of Split and Threshold Graphs

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.

preprint2012arXiv

Rainbow Connection Number and Radius

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.

preprint2011arXiv

A Constant Factor Approximation Algorithm for Boxicity of Circular Arc Graphs

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 - ε})$ -factor, for any $ε>0$ in polynomial time unless $NP=ZPP$ . Till date, there is no well known graph class of unbounded boxicity for which even an $n^ε$ -factor approximation algorithm for computing boxicity is known, for any $ε<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.

preprint2011arXiv

On Rainbow Connection Number and Connectivity

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 $δ$ , the rainbow connection number is upper bounded by $3n/(δ+ 1) + 3$ [Chandran et al., 2010]. This directly gives an upper bound of $3n/(λ+ 1) + 3$ and $3n/(κ+ 1) + 3$ for rainbow connection number where $λ$ and $κ$ , 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 + ε)n/κ+ 23/ ε^2$ , for any $ε> 0$ . We conjecture that rainbow connection number is upper bounded by $n/κ+ O(1)$ and show that it is true for $κ= 2$ . We also show that the conjecture is true for chordal graphs and graphs of girth at least 7.

preprint2011arXiv

On the SIG dimension of trees under $L_{\infty}$ metric

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 $α(T) = \max_{x \in V(T)}$ leaf-degree $(x)$ . Let $S = \{v\in V(T) |$ leaf-degree $(v) = α\}$ . If $|S| = 1$ , we define $β(T) = α(T) - 1$ . Otherwise define $β(T) = α(T)$ . We show that for a tree $T$ , $SIG_\infty(T) = \lceil \log_2(β+ 2)\rceil$ where $β= β(T)$ , provided $β$ is not of the form $2^k - 1$ , for some positive integer $k \geq 1$ . If $β= 2^k - 1$ , then $SIG_\infty (T) \in \{k, k+1\}$ . We show that both values are possible.

preprint2011arXiv

Rainbow Connection Number of Graph Power and Graph Products

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.

preprint2011arXiv

Representing a cubic graph as the intersection graph of axis-parallel boxes in three dimensions

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.

preprint2010arXiv

Acyclic Edge Coloring of Triangle Free Planar Graphs

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 much earlier by Fiamcik) that $a'(G)\le Δ+2$ , where $Δ=Δ(G)$ denotes the maximum degree of the graph. If every induced subgraph $H$ of $G$ satisfies the condition $\vert E(H) \vert \le 2\vert V(H) \vert -1$ , we say that the graph $G$ satisfies $Property\ A$ . In this paper, we prove that if $G$ satisfies $Property\ A$ , then $a'(G)\le Δ+ 3$ . Triangle free planar graphs satisfy $Property\ A$ . We infer that $a'(G)\le Δ+ 3$ , if $G$ is a triangle free planar graph. Another class of graph which satisfies $Property\ A$ is 2-fold graphs (union of two forests).

preprint2010arXiv

Boxicity and Poset Dimension

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)/(χ(G_\poset)-1) \le \dim(\poset)\le 2\boxi(G_\poset)$, where $χ(G_\poset)$ is the chromatic number of $G_\poset$ and $χ(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 $Δ$ is $O(Δ\log^2Δ)$ which is an improvement over the best known upper bound of $Δ^2+2$ . (2) There exist graphs with boxicity $Ω(Δ\logΔ)$ . This disproves a conjecture that the boxicity of a graph is $O(Δ)$ . (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-ε})$ for any $ε>0$ , unless $NP=ZPP$ .

preprint2010arXiv

Boxicity of Line Graphs

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Δ(\lceil log_2(log_2(Δ)) \rceil + 3) + 1, where Δdenotes the maximum degree of G. Since Δ<= 2(χ- 1), for any line graph G with chromatic number χ, box(G) = O(χlog_2(log_2(χ))). 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).

preprint2010arXiv

Rainbow Connection Number and Connected Dominating Sets

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 γ_c(G) + 2, where γ_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 δ, the rainbow connection number is upper bounded by 3n/(δ + 1) + 3. This solves an open problem of Schiermeyer (2009), improving the previously best known bound of 20n/δ 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).

preprint2010arXiv

The Hardness of Approximating the Threshold Dimension, Boxicity and Cubicity of a Graph

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-ε})$ for any $ε>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-ε})$ for any $ε>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.

preprint2008arXiv

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

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 Δ+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 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.

L. Sunil Chandran

Research overview

Is this your work?

32 publications

New bounds on the anti-Ramsey numbers of star graphs

Weakening Total Coloring Conjecture: Weak TCC and Hadwiger's Conjecture on Total Graphs

Upper Bounding Rainbow Connection Number by Forest Number

Sublinear Approximation Algorithms for Boxicity and Related Problems

2-connecting Outerplanar Graphs without Blowing Up the Pathwidth

Boxicity and separation dimension

On Additive Combinatorics of Permutations of \mathbb{Z}_n

Parameterized and Approximation Algorithms for Boxicity

Rainbow Colouring of Split Graphs

Separation dimension of bounded degree graphs

Separation dimension of sparse graphs

Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

Boxicity and Cubicity of Product Graphs

Bipartite powers of k-chordal graphs

Cubicity, Degeneracy, and Crossing Number

Isoperimetric Sequences for Infinite Complete Binary Trees, Meta-Fibonacci Sequences and Signed Almost Binary Partitions

Lower Bounds for Boxicity

Pairwise Suitable Family of Permutations and Boxicity

Product Dimension of Forests and Bounded Treewidth Graphs

Rainbow Colouring of Split and Threshold Graphs

Rainbow Connection Number and Radius

A Constant Factor Approximation Algorithm for Boxicity of Circular Arc Graphs

On Rainbow Connection Number and Connectivity

On the SIG dimension of trees under $L_{\infty}$ metric

Rainbow Connection Number of Graph Power and Graph Products

Representing a cubic graph as the intersection graph of axis-parallel boxes in three dimensions

Acyclic Edge Coloring of Triangle Free Planar Graphs

Boxicity and Poset Dimension

Boxicity of Line Graphs

Rainbow Connection Number and Connected Dominating Sets

The Hardness of Approximating the Threshold Dimension, Boxicity and Cubicity of a Graph

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

See the researcher in context

Building this map preview

L. Sunil Chandran

Research overview

Is this your work?

32 publications

New bounds on the anti-Ramsey numbers of star graphs

Weakening Total Coloring Conjecture: Weak TCC and Hadwiger's Conjecture on Total Graphs

Upper Bounding Rainbow Connection Number by Forest Number

Sublinear Approximation Algorithms for Boxicity and Related Problems

2-connecting Outerplanar Graphs without Blowing Up the Pathwidth

Boxicity and separation dimension

On Additive Combinatorics of Permutations of \mathbb{Z}_n

Parameterized and Approximation Algorithms for Boxicity

Rainbow Colouring of Split Graphs

Separation dimension of bounded degree graphs

Separation dimension of sparse graphs

Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

Boxicity and Cubicity of Product Graphs

Bipartite powers of k-chordal graphs

Cubicity, Degeneracy, and Crossing Number

Isoperimetric Sequences for Infinite Complete Binary Trees, Meta-Fibonacci Sequences and Signed Almost Binary Partitions

Lower Bounds for Boxicity

Pairwise Suitable Family of Permutations and Boxicity

Product Dimension of Forests and Bounded Treewidth Graphs

Rainbow Colouring of Split and Threshold Graphs

Rainbow Connection Number and Radius

A Constant Factor Approximation Algorithm for Boxicity of Circular Arc Graphs

On Rainbow Connection Number and Connectivity

On the SIG dimension of trees under L∞L_{\infty}L∞​ metric

Rainbow Connection Number of Graph Power and Graph Products

Representing a cubic graph as the intersection graph of axis-parallel boxes in three dimensions

Acyclic Edge Coloring of Triangle Free Planar Graphs

Boxicity and Poset Dimension

Boxicity of Line Graphs

Rainbow Connection Number and Connected Dominating Sets

The Hardness of Approximating the Threshold Dimension, Boxicity and Cubicity of a Graph

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

See the researcher in context

Building this map preview

On the SIG dimension of trees under $L_{\infty}$ metric

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