A short note on conflict‐free coloring on closed neighborhoods of bounded degree graphs
Sriram Bhyravarapu, Subrahmanyam Kalyanasundaram, Rogers Mathew
Abstract
Abstract The closed neighborhood conflict‐free chromatic number of a graph , denoted by , is the minimum number of colors required to color the vertices of such that for every vertex, there is a color that appears exactly once in its closed neighborhood. Pach and Tardos showed that , for any , where is the maximum degree. In 2014, Glebov et al. showed existence of graphs with . In this article, we bridge the gap between the two bounds by showing that .
Topics & Concepts
CombinatoricsMathematicsBounded functionDegree (music)Vertex (graph theory)Brooks' theoremChromatic scaleGraphDiscrete mathematics1-planar graphChordal graphAcousticsPhysicsMathematical analysisAdvanced Graph Theory ResearchComputational Geometry and Mesh GenerationLimits and Structures in Graph Theory