# Coloring where all colors are present in closed neighborhood of every vertex

I am interested in (proper) vertex colorings of graphs with the following condition:
for every vertex $$v$$ in the graph, all colors should be present in the closed neighborhood of $$v$$.

Is this studied in the literature? The closest I found is $$r$$-dynamic $$k$$-coloring. For $$k$$-regular graphs, a ($$k-1$$)-dynamic $$k$$-coloring satisfies the above condition. But, I am also interested in a coloring that use less than $$k$$ colors and satisfies the above condition. Currently, I am more interested in such coloring of regular graphs.

If there is a paper dealing with ($$k-1$$)-dynamic $$k$$-colorings of $$k$$-regular graphs, I would like to read it (I saw a result on ($$k+1$$)-dynamic $$k$$-colorings in a paper).

Thank you.

Related Colouring Variants:-

1. $$r$$-dynamic $$k$$-coloring (also called $$r$$-hued $$k$$-coloring)
An $$r$$-dynamic $$k$$-coloring of $$G$$ is a (proper) $$k$$-coloring of $$G$$ such that every vertex $$v$$ in $$G$$ has neighbors in at least $$\min\{deg(v),r\}$$ different color classes.
2. b-coloring
A b-coloring is a (proper) coloring such that every color class $$V_i$$ contains a vertex $$u_i$$ which has neighbors in all other color classes.
In the coloring variant I am looking for, every vertex has neighbors in all other color classes.

Definition:-
For a vertex $$v$$ of $$G$$, the closed neighborhood of $$G$$, denoted by $$N[v]$$, is $$v$$ together with its set of neighbors.
i.e., $$N[v]=\{v\}\cup\{u : uv\in E(G)\}$$.

I would call this a polychromatic coloring of the closed neighborhood hypergraph. I don't think this has been studied before for general graphs.

Here is a paper studying the question when edges are colored:
Béla Bollobás, David Pritchard, Thomas Rothvoß, Alex Scott: Cover-Decomposition and Polychromatic Numbers

And here is one that studies the conflict-free coloring problem for your hypergraph:
Sriram Bhyravarapu, Subrahmanyam Kalyanasundaram, Rogers Mathew: Conflict-free coloring on closed neighborhoods of bounded degree graphs

If you replace closed neighborhood with geometric range spaces, then you can find a lot more literature, most notably my own amazing papers.

It is studied in the literature. It is the coloring variant called fall coloring introduced by Dunbar et al [1].

Quote from [1] (I have made minute changes in the language):

A coloring of a graph $$G=(V,E)$$ is a partition $$\Pi=\{V_1,V_2,\dots,V_k\}$$ of the vertices of G into independent sets $$V_i$$, or color classes. A vertex $$v\in V_i$$ is called colorful if it is adjacent to at least one vertex in every color class $$V_j$$, $$j\neq i$$. A fall coloring is a coloring in which every vertex is colorful. If a graph G has a fall coloring, the fall chromatic number of G is the minimum number of colors for a fall coloring of G.

Interestingly, the fall chromatic number of $$G$$ is equal to the maximum number of independent dominating sets into which the vertex set of $$G$$ can be partitioned (the latter is called the idomatic number of $$G$$). Note that an independent dominating set of $$G$$ is precisely a maximal independent set of $$G$$.

url for list of papers that cited [1] (according to google scholar): https://scholar.google.com/scholar?cites=6893367022071411040&as_sdt=2005&sciodt=0,5&hl=en

[1] Dunbar, J. E.; Hedetniemi, S. M.; Hedetniemi, S. T.; Jacobs, D. P.; Knisely, J.; Laskar, R. C.; Rall, D. F., Fall colorings of graphs, J. Comb. Math. Comb. Comput. 33, 257-273 (2000). ZBL0962.05020.

• Another name used in the literature is frozen coloring. Dec 27, 2023 at 11:52