BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Manu Basavaraju

Manu Basavaraju contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.CODiscrete Mathematics

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
8works
0followers
2topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

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

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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&#39;(G)$. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that $a&#39;(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&#39;(G)\le Δ+ 3$. Triangle free planar graphs satisfy $Property\ A$. We infer that $a&#39;(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).

0 citations0 reviewsNo code linkedOpen access
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&#39;(G)$. It was conjectured by Alon, Sudakov and Zaks (and earlier by Fiamcik) that $a&#39;(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&#39;(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.

0 citations0 reviewsNo code linkedOpen access