BZPEER

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

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

Approximating the Cubicity of Trees

Cubicity of a graph $G$ is the smallest dimension $d$ , for which $G$ is a unit disc graph in ${\mathbb{R}}^d$ , under the $l^\infty$ metric, i.e. $G$ can be represented as an intersection graph of $d$ -dimensional (axis-parallel) unit hypercubes. We call such an intersection representation a $d$ -dimensional cube representation of $G$ . Computing cubicity is known to be inapproximable in polynomial time, within an $O(n^{1-ε})$ factor for any $ε>0$ , unless NP=ZPP. In this paper, we present a randomized algorithm that runs in polynomial time and computes cube representations of trees, of dimension within a constant factor of the optimum. It is also shown that the cubicity of trees can be approximated within a constant factor in deterministic polynomial time, if the cube representation is not required to be computed. As far as we know, this is the first constant factor approximation algorithm for computing the cubicity of trees. It is not yet clear whether computing the cubicity of trees is NP-hard or not.

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

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.

preprint2013arXiv

Maximal induced matchings in triangle-free graphs

An induced matching in a graph is a set of edges whose endpoints induce a $1$ -regular subgraph. It is known that any $n$ -vertex graph has at most $10^{n/5} \approx 1.5849^n$ maximal induced matchings, and this bound is best possible. We prove that any $n$ -vertex triangle-free graph has at most $3^{n/3} \approx 1.4423^n$ maximal induced matchings, and this bound is attained by any disjoint union of copies of the complete bipartite graph $K_{3,3}$ . Our result implies that all maximal induced matchings in an $n$ -vertex triangle-free graph can be listed in time $O(1.4423^n)$ , yielding the fastest known algorithm for finding a maximum induced matching in a triangle-free graph.

preprint2013arXiv

Strong chromatic index of chordless graphs

A strong edge colouring of a graph is an assignment of colours to the edges of the graph such that for every colour, the set of edges that are given that colour form an induced matching in the graph. The strong chromatic index of a graph $G$ , denoted by $χ'_s(G)$ , is the minimum number of colours needed in any strong edge colouring of $G$ . A graph is said to be \emph{chordless} if there is no cycle in the graph that has a chord. Faudree, Gyárfás, Schelp and Tuza~[The Strong Chromatic Index of Graphs, Ars Combin., 29B (1990), pp.~205--211] considered a particular subclass of chordless graphs, namely the class of graphs in which all the cycle lengths are multiples of four, and asked whether the strong chromatic index of these graphs can be bounded by a linear function of the maximum degree. Chang and Narayanan~[Strong Chromatic Index of 2-degenerate Graphs, J. Graph Theory, 73(2) (2013), pp.~119--126] answered this question in the affirmative by proving that if $G$ is a chordless graph with maximum degree $Δ$ , then $χ'_s(G) \leq 8Δ-6$ . We improve this result by showing that for every chordless graph $G$ with maximum degree $Δ$ , $χ'_s(G)\leq 3Δ$ . This bound is tight up to to an additive constant.

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

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

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.

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).

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.

Manu Basavaraju

Research overview

Is this your work?

13 publications

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

2-connecting Outerplanar Graphs without Blowing Up the Pathwidth

Approximating the Cubicity of Trees

Boxicity and separation dimension

Separation dimension of bounded degree graphs

Separation dimension of sparse graphs

Maximal induced matchings in triangle-free graphs

Strong chromatic index of chordless graphs

Pairwise Suitable Family of Permutations and Boxicity

Rainbow Connection Number and Radius

Rainbow Connection Number of Graph Power and Graph Products

Acyclic Edge Coloring of Triangle Free Planar Graphs

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

See the researcher in context

Building this map preview

Manu Basavaraju

Research overview

Is this your work?

13 publications

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

2-connecting Outerplanar Graphs without Blowing Up the Pathwidth

Approximating the Cubicity of Trees

Boxicity and separation dimension

Separation dimension of bounded degree graphs

Separation dimension of sparse graphs

Maximal induced matchings in triangle-free graphs

Strong chromatic index of chordless graphs

Pairwise Suitable Family of Permutations and Boxicity

Rainbow Connection Number and Radius

Rainbow Connection Number of Graph Power and Graph Products

Acyclic Edge Coloring of Triangle Free Planar Graphs

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

See the researcher in context

Building this map preview

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