2026-07-23T05:50:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16817 2024-03-06T10:58:24Z ddc:004 open_access

Conflict-Free Coloring on Claw-Free Graphs and Interval Graphs Bhyravarapu, Sriram Kalyanasundaram, Subrahmanyam Mathew, Rogers Conflict-free coloring Interval graphs Bipartite graphs Claw-free graphs 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 χ_{ON}^*(G). The analogous notion for closed neighborhood is called CFCN^* coloring and the analogous parameter is denoted by χ_{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 K_{1,k}-free graph then χ_{ON}^*(G) = O(k²log Δ), where Δ denotes the maximum degree of G. Dębski and Przybyło in [J. Graph Theory, 2021] had shown that if G is a line graph, then χ_{CN}^*(G) = O(log Δ). As an open question, they had asked if their result could be extended to claw-free (K_{1,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 Dębski and Przybyło. - We show that if the minimum degree of any vertex in G is Ω(Δ/{log^ε Δ}) for some ε ≥ 0, then χ_{ON}^*(G) = O(log^{1+ε}Δ). This is a generalization of the result given by Dębski and Przybyło in the same paper where they showed that if the minimum degree of any vertex in G is Ω(Δ), then χ_{ON}^*(G)= O(logΔ). - We give a polynomial time algorithm to compute χ_{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 χ_{ON}^*(G) = k where k ∈ {1, 2, 3}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sriram Bhyravarapu and Subrahmanyam Kalyanasundaram and Rogers Mathew 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.19 urn:nbn:de:0030-drops-168173 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.19 eng https://creativecommons.org/licenses/by/4.0/legalcode