Source author record

Sriram Bhyravarapu

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms Discrete Mathematics

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Combinatorial Bounds for Conflict-free Coloring on Open Neighborhoods

In an undirected graph $G$ , a conflict-free coloring with respect to open neighborhoods (denoted by CFON coloring) is an assignment of colors to the vertices such that every vertex has a uniquely colored vertex in its open neighborhood. The minimum number of colors required for a CFON coloring of $G$ is the CFON chromatic number of $G$ , denoted by $χ_{ON}(G)$ . The decision problem that asks whether $χ_{ON}(G) \leq k$ is NP-complete. We obtain the following results: * Bodlaender, Kolay and Pieterse [WADS 2019] showed the upper bound $χ_{ON}(G)\leq {\sf fvs}(G)+3$ , where ${\sf fvs}(G)$ denotes the size of a minimum feedback vertex set of $G$ . We show the improved bound of $χ_{ON}(G)\leq {\sf fvs}(G)+2$ , which is tight, thereby answering an open question in the above paper. * We study the relation between $χ_{ON}(G)$ and the pathwidth of the graph $G$ , denoted ${\sf pw}(G)$ . The above paper from WADS 2019 showed the upper bound $χ_{ON}(G) \leq 2{\sf tw}(G)+1$ where ${\sf tw}(G)$ stands for the treewidth of $G$ . This implies an upper bound of $χ_{ON}(G) \leq 2{\sf pw}(G)+1$ . We show an improved bound of $χ_{ON}(G) \leq \lfloor \frac{5}{3}({\sf pw}(G)+1) \rfloor$ . * We prove new bounds for $χ_{ON}(G)$ with respect to the structural parameters neighborhood diversity and distance to cluster, improving existing results. * We also study the partial coloring variant of the CFON coloring problem, which allows vertices to be left uncolored. Let $χ^*_{ON}(G)$ denote the minimum number of colors required to color $G$ as per this variant. Abel et. al. [SIDMA 2018] showed that $χ^*_{ON}(G) \leq 8$ when $G$ is planar. They asked if fewer colors would suffice for planar graphs. We answer this question by showing that $χ^*_{ON}(G) \leq 5$ for all planar $G$ . All our bounds are a result of constructive algorithmic procedures.

preprint2020arXiv

Conflict-Free Coloring of Star-Free Graphs on Open Neighborhoods

Given a graph, the conflict-free coloring problem on open neighborhoods (CFON) asks to color the vertices of the graph so that all the vertices have a uniquely colored vertex in its open neighborhood. The smallest number of colors required for such a coloring is called the conflict-free chromatic number and denoted $χ_{ON}(G)$ . In this note, we study this problem on $S_k$ -free graphs where $S_k$ is a star on $k+1$ vertices. When $G$ is $S_k$ -free, we show that $χ_{ON}(G) = O(k\cdot \log^{2+ε}Δ)$ , for any $ε> 0$ , where $Δ$ denotes the maximum degree of $G$ . Further, we show existence of claw-free ( $S_3$ -free) graphs that require $Ω(\log Δ)$ colors.

preprint2020arXiv

Conflict-free coloring on closed neighborhoods of bounded degree graphs

The closed neighborhood conflict-free chromatic number of a graph $G$ , denoted by $χ_{CN}(G)$ , is the minimum number of colors required to color the vertices of $G$ such that for every vertex, there is a color that appears exactly once in its closed neighborhood. Pach and Tardos [Combin. Probab. Comput. 2009] showed that $χ_{CN}(G) = O(\log^{2+\varepsilon} Δ)$ , for any $\varepsilon > 0$ , where $Δ$ is the maximum degree. In [Combin. Probab. Comput. 2014], Glebov, Szabó and Tardos showed existence of graphs $G$ with $χ_{CN}(G) = Ω(\log^2Δ)$ . In this paper, we bridge the gap between the two bounds by showing that $χ_{CN}(G) = O(\log^2 Δ)$ .

preprint2018arXiv

On the Tractability of (k,i)-Coloring

In an undirected graph, a proper (k,i)-coloring is an assignment of a set of k colors to each vertex such that any two adjacent vertices have at most i common colors. The (k,i)-coloring problem is to compute the minimum number of colors required for a proper (k,i)-coloring. This is a generalization of the classic graph coloring problem. We show a parameterized algorithm for the (k,i)-coloring problem with the size of the feedback vertex set as a parameter. Our algorithm does not use tree-width machinery, thus answering a question of Majumdar, Neogi, Raman and Tale [CALDAM 2017]. We also give a faster and simpler exact algorithm for (k, k-1)-coloring. From the hardness perspective, we show that the (k,i)-coloring problem is NP-complete for any fixed values i, k, whenever i<k, thereby settling a conjecture of Mendez-Diaz and Zabala [1999] and again asked by Majumdar, Neogi, Raman and Tale. The NP-completeness result improves the partial NP-completeness shown in the preliminary version of this paper published in CALDAM 2018.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

Sriram Bhyravarapu

Research overview

Is this your work?

4 publications

Combinatorial Bounds for Conflict-free Coloring on Open Neighborhoods

Conflict-Free Coloring of Star-Free Graphs on Open Neighborhoods

Conflict-free coloring on closed neighborhoods of bounded degree graphs

On the Tractability of (k,i)-Coloring

See the researcher in context

Building this map preview