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.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.