Conflict-Free Coloring on Claw-Free Graphs and Interval Graphs

Bhyravarapu, S. and Kalyanasundaram, Subrahmanyam and Mathew, Rogers (2022) Conflict-Free Coloring on Claw-Free Graphs and Interval Graphs. In: 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, 22 August 2022 through 26 August 2022, Vienna.

Text
LIPIcs_.pdf - Published Version
Available under License Creative Commons Attribution.
Download (713kB)

Abstract

A Conflict-Free Open Neighborhood coloring, abbreviated CFON*coloring, of a graph G = (V,E) using k colors is an assignment of colors from a set of k colors to a subset of vertices of V (G) such that every vertex sees some color exactly once in its open neighborhood. The minimum k for which G has a CFON*coloring using k colors is called the CFON*chromatic number of G, denoted by X*ON(G). The analogous notion for closed neighborhood is called CFCN*coloring and the analogous parameter is denoted by X*CN(G). The problem of deciding whether a given graph admits a CFON*(or CFCN*) coloring that uses k colors is NP-complete. Below, we describe briefly the main results of this paper. For k ≥ 3, we show that if G is a K1,k-free graph then X*ON(G)= O(k2 log Δ), where Δ denotes the maximum degree of G. Debski and Przybylo in [J. Graph Theory, 2021] had shown that if G is a line graph, then X*CN(G)= O(log Δ). As an open question, they had asked if their result could be extended to claw-free (K1,3-free) graphs, which are a superclass of line graphs. Since it is known that the CFCN*chromatic number of a graph is at most twice its CFON*chromatic number, our result positively answers the open question posed by Debski and Przybyło. We show that if the minimum degree of any vertex in G is Ω(Δ logϵ Δ) for some ϵ ≥ 0, then X*ON(G)= O(log1+ϵ Δ). This is a generalization of the result given by Debski and Przybyło in the same paper where they showed that if the minimum degree of any vertex in G is Ω(Δ), then X*ON(G)= O(log Δ). We give a polynomial time algorithm to compute X*ON(G) for interval graphs G. This answers in positive the open question posed by Reddy [Theoretical Comp. Science, 2018] to determine whether the CFON*chromatic number can be computed in polynomial time on interval graphs. We explore biconvex graphs, a subclass of bipartite graphs and give a polynomial time algorithm to compute their CFON*chromatic number. This is interesting as Abel et al. [SIDMA, 2018] had shown that it is NP-complete to decide whether a planar bipartite graph G has X*ON(G) = k where k ∈ {1, 2, 3}. © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

[error in script]

IITH Creators: