A tight bound for conflict-free coloring in terms of distance to cluster |
| |
Institution: | 1. The Institute of Mathematical Sciences, HBNI, Chennai, India;2. Department of Computer Science and Engineering, IIT Hyderabad, India |
| |
Abstract: | Given an undirected graph , a conflict-free coloring with respect to open neighborhoods (CFON coloring) is a vertex coloring such that every vertex has a uniquely colored vertex in its open neighborhood. The minimum number of colors required for such a coloring is the CFON chromatic number of G, denoted by .In previous work WG 2020], we showed the upper bound , where denotes the distance to cluster parameter of G. In this paper, we obtain the improved upper bound of . We also exhibit a family of graphs for which , thereby demonstrating that our upper bound is tight. |
| |
Keywords: | Conflict-free coloring Distance to cluster Graph coloring |
本文献已被 ScienceDirect 等数据库收录! |
|