2020/07/10 by Bhyravarapu, Sriram, Kalyanasundaram, Subrahmanyam
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2007.05585
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) ≤ k is NP-complete. We obtain the following results: * Bodlaender, Kolay and Pieterse [WADS 2019] showed the upper bound χON(G)≤ \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)≤ \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) ≤ 2\sf tw(G)+1 where \sf tw(G) stands for the treewidth of G. This implies an upper bound of χON(G) ≤ 2\sf pw(G)+1. We show an improved bound of χON(G) ≤ \lfloor (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) ≤ 8 when G is planar. They asked if fewer colors would suffice for planar graphs. We answer this question by showing that χ^*ON(G) ≤ 5 for all planar G. All our bounds are a result of constructive algorithmic procedures.