
doi: 10.1002/jgt.22743
AbstractA vertex coloring of a given graph is conflict‐free if the closed neighborhood of every vertex contains a unique color (i.e., a color appearing only once in the neighborhood). The minimum number of colors in such a coloring is the conflict‐free chromatic number of , denoted . What is the maximum possible conflict‐free chromatic number of a graph with a given maximum degree ? Trivially, , but it is far from optimal—due to results of Glebov, Szabó, and Tardos, and of Bhyravarapu, Kalyanasundaram, and Mathew, the answer is known to be . We show that the answer to the same question in the class of line graphs is —it follows that the extremal value of the conflict‐free chromatic index among graphs with maximum degree is much smaller than the one for conflict‐free chromatic number. The same result for is also provided in the class of near regular graphs, that is, graphs with minimum degree .
Coloring of graphs and hypergraphs, Graph operations (line graphs, products, etc.), line graphs, conflict-free chromatic number
Coloring of graphs and hypergraphs, Graph operations (line graphs, products, etc.), line graphs, conflict-free chromatic number
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 9 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
