Conflict-Free Coloring Bounds on Open Neighborhoods

Bhyravarapu, Sriram and Kalyanasundaram, Subrahmanyam and Mathew, R. (2022) Conflict-Free Coloring Bounds on Open Neighborhoods. Algorithmica. ISSN 0178-4617

Full text not available from this repository. (Request a copy)

Abstract

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. Structural as well as algorithmic aspects of this problem have been well studied. We obtain the following results for χON(G) :Bodlaender, Kolay and Pieterse (WADS 2019) showed the upper bound χON(G) ≤ fvs(G) + 3 , where fvs(G) denotes the size of a minimum feedback vertex set of G. We show the improved bound of χON(G) ≤ 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 pw(G). The above paper from WADS 2019 showed the upper bound χON(G) ≤ 2 tw(G) + 1 where tw(G) stands for the treewidth of G. This implies an upper bound of χON(G) ≤ 2 pw(G) + 1. We show an improved bound of χON(G)≤⌊53(pw(G)+1)⌋.We prove new bounds for χON(G) with respect to the structural parameters neighborhood diversity and distance to cluster, improving the existing results of Gargano and Rescigno (Theor. Comput. Sci. 2015) and Reddy (Theor. Comput. Sci. 2018), respectively. Furthermore, our techniques also yield improved bounds for the closed neighborhood variant of the problem.We prove bounds for Sk-free graphs where Sk is a star on k+ 1 vertices. For a graph G with maximum degree Δ , it is known that χON(G) ≤ Δ + 1 and this bound is tight in general. When G is Sk-free, we show that χON(G) = O(k· log 2+ϵΔ) , for any ϵ> 0. In particular, when G is claw-free, this implies that χON(G) = O(log 2+ϵΔ). Further, we show existence of claw-free graphs that require Ω (log Δ) colors.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. This approach also yields the bound χON∗(G)≤4 for all outerplanar G. All our bounds are a result of constructive algorithmic procedures. © 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

[error in script]

IITH Creators:

IITH Creators	ORCiD
Kalyanasundaram, Subrahmanyam	UNSPECIFIED
Mathew, R.	https://orcid.org/0000-0003-4536-1136

Item Type:

Article

Additional Information:

We would like to thank N. R. Aravind for helpful discussions. We would also like to thank the anonymous reviewer of WG2020 who pointed out an issue with the proof of Theorem . The second author acknowledges DST-SERB (MTR/2020/000497) for supporting this research. The third author acknowledges DST-SERB (MTR/2019/000550) for supporting this research.

Uncontrolled Keywords:

Algorithmic aspects; Conflict-Free Colorings; Decision problems; Graph G; Minimum feedback vertex set; Neighbourhood; NP Complete; Structural aspects; Undirected graph; Upper Bound

Subjects:

Computer science

Divisions:

Department of Computer Science & Engineering

Depositing User:

. LibTrainee 2021

Date Deposited:

21 Jul 2022 07:23

Last Modified:

21 Jul 2022 07:23

URI:

http://raiithold.iith.ac.in/id/eprint/9838