Abstract
A ConflictFree 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 NPcomplete. 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 clawfree (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 NPcomplete to decide whether a planar bipartite graph G has χ_{ON}^*(G) = k where k ∈ {1, 2, 3}.
BibTeX  Entry
@InProceedings{bhyravarapu_et_al:LIPIcs.MFCS.2022.19,
author = {Bhyravarapu, Sriram and Kalyanasundaram, Subrahmanyam and Mathew, Rogers},
title = {{ConflictFree Coloring on ClawFree Graphs and Interval Graphs}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {19:119:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772563},
ISSN = {18688969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16817},
URN = {urn:nbn:de:0030drops168173},
doi = {10.4230/LIPIcs.MFCS.2022.19},
annote = {Keywords: Conflictfree coloring, Interval graphs, Bipartite graphs, Clawfree graphs}
}
Keywords: 

Conflictfree coloring, Interval graphs, Bipartite graphs, Clawfree graphs 
Collection: 

47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) 
Issue Date: 

2022 
Date of publication: 

22.08.2022 