A short note on conflict-free coloring on closed neighborhoods of bounded degree graphs

Bhyravarapu, S. and Kalyanasundaram, S. and Mathew, R. (2021) A short note on conflict-free coloring on closed neighborhoods of bounded degree graphs. Journal of Graph Theory, 97 (4). pp. 553-556. ISSN 03649024

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


he closed neighborhood conflict-free chromatic number of a graph (Formula presented.), denoted by (Formula presented.), is the minimum number of colors required to color the vertices of (Formula presented.) such that for every vertex, there is a color that appears exactly once in its closed neighborhood. Pach and Tardos showed that (Formula presented.), for any (Formula presented.), where (Formula presented.) is the maximum degree. In 2014, Glebov et al. showed existence of graphs (Formula presented.) with (Formula presented.). In this article, we bridge the gap between the two bounds by showing that (Formula presented.).

[error in script]
IITH Creators:
IITH CreatorsORCiD
Kalyanasundaram, SubrahmanyamUNSPECIFIED
Item Type: Article
Uncontrolled Keywords: Bounded degree graphs, Chromatic number of a graphs, Conflict free, Conflict-Free Colorings, Maximum degree
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Mrs Haseena VKKM
Date Deposited: 02 Nov 2021 10:38
Last Modified: 02 Mar 2022 09:21
URI: http://raiith.iith.ac.in/id/eprint/8883
Publisher URL: https://onlinelibrary.wiley.com/doi/10.1002/jgt.22...
OA policy: https://v2.sherpa.ac.uk/id/publication/15126
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 8883 Statistics for this ePrint Item