<p>It is studied in the literature. It is the coloring variant called fall coloring introduced by Dunbar et al [1].</p>
<p>Quote from [1] (I have made minute changes in the language):</p>
<blockquote>
<p>A coloring of a graph <span class="math-container">$G=(V,E)$</span> is a partition <span class="math-container">$\Pi=\{V_1,V_2,\dots,V_k\}$</span> of the vertices of G into independent sets <span class="math-container">$V_i$</span>, or color classes. A vertex <span class="math-container">$v\in V_i$</span> is called colorful if it is adjacent to at least one vertex in every color class <span class="math-container">$V_j$</span>, <span class="math-container">$j\neq i$</span>. 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.</p>
</blockquote>
<p>Interestingly, the fall chromatic number of <span class="math-container">$G$</span> is equal to the maximum number of independent dominating sets into which the vertex set of <span class="math-container">$G$</span> can be partitioned (the latter is called the idomatic number of <span class="math-container">$G$</span>). Note that an independent dominating set of <span class="math-container">$G$</span> is precisely a maximal independent set of <span class="math-container">$G$</span>.</p>
<p>url for list of papers that cited [1] (according to google scholar):
<a href="https://scholar.google.com/scholar?cites=6893367022071411040&amp;as_sdt=2005&amp;sciodt=0,5&amp;hl=en" rel="nofollow noreferrer">https://scholar.google.com/scholar?cites=6893367022071411040&amp;as_sdt=2005&amp;sciodt=0,5&amp;hl=en</a></p>
<p>[1] <em>Dunbar, J. E.; Hedetniemi, S. M.; Hedetniemi, S. T.; Jacobs, D. P.; Knisely, J.; Laskar, R. C.; Rall, D. F.</em>, Fall colorings of graphs, J. Comb. Math. Comb. Comput. 33, 257-273 (2000). <a href="https://zbmath.org/?q=an:0962.05020" rel="nofollow noreferrer">ZBL0962.05020</a>.</p>

CC BY-SA 4.0
2023-12-27T11:52:19.623Z
Another name used in the literature is frozen coloring.
Cyriac Antony
CC BY-SA 4.0
2020-11-14T15:17:26.513Z
2020-11-14T15:17:26.513Z
Cyriac Antony
<p>I would call this a polychromatic coloring of the closed neighborhood hypergraph.
I don't think this has been studied before for general graphs.</p>
<p>Here is a paper studying the question when edges are colored:<br />
<a href="https://arxiv.org/abs/1009.6144" rel="nofollow noreferrer">Béla Bollobás, David Pritchard, Thomas Rothvoß, Alex Scott: Cover-Decomposition and Polychromatic Numbers</a></p>
<p>And here is one that studies the conflict-free coloring problem for your hypergraph:<br />
<a href="https://arxiv.org/abs/2003.05637" rel="nofollow noreferrer">Sriram Bhyravarapu, Subrahmanyam Kalyanasundaram, Rogers Mathew: Conflict-free coloring on closed neighborhoods of bounded degree graphs</a></p>
<p>If you replace closed neighborhood with geometric range spaces, then you can find a lot more literature, most notably my own amazing papers.</p>

CC BY-SA 4.0
2020-11-13T08:22:12.273Z
2020-11-13T08:22:12.273Z
domotorp
<p>I am interested in (proper) vertex colorings of graphs with the following condition:<br />
for every vertex <span class="math-container">$v$</span> in the graph, all colors should be present in the <em>closed neighborhood</em> of <span class="math-container">$v$</span>.</p>
<p><strong>Is this studied in the literature?</strong> The closest I found is <span class="math-container">$r$</span>-dynamic <span class="math-container">$k$</span>-coloring. For <span class="math-container">$k$</span>-regular graphs, a (<span class="math-container">$k-1$</span>)-dynamic <span class="math-container">$k$</span>-coloring satisfies the above condition. But, I am also interested in a coloring that use less than <span class="math-container">$k$</span> colors and satisfies the above condition. Currently, I am more interested in such coloring of regular graphs.</p>
<p>If there is a paper dealing with (<span class="math-container">$k-1$</span>)-dynamic <span class="math-container">$k$</span>-colorings of <span class="math-container">$k$</span>-regular graphs, I would like to read it (I saw a result on (<span class="math-container">$k+1$</span>)-dynamic <span class="math-container">$k$</span>-colorings in a paper).</p>
<p>Thank you.</p>
<p><em>Related Colouring Variants</em>:-</p>
<ol>
<li><span class="math-container">$r$</span>-dynamic <span class="math-container">$k$</span>-coloring (also called <span class="math-container">$r$</span>-hued <span class="math-container">$k$</span>-coloring)<br />
An <span class="math-container">$r$</span>-dynamic <span class="math-container">$k$</span>-coloring of <span class="math-container">$G$</span> is a (proper) <span class="math-container">$k$</span>-coloring of <span class="math-container">$G$</span> such that every vertex <span class="math-container">$v$</span> in <span class="math-container">$G$</span> has neighbors in at least <span class="math-container">$\min\{deg(v),r\}$</span> different color classes.</li>
<li>b-coloring<br />
A b-coloring is a (proper) coloring such that every color class <span class="math-container">$V_i$</span> contains a vertex <span class="math-container">$u_i$</span> which has neighbors in all other color classes.<br />
In the coloring variant I am looking for, every vertex has neighbors in all other color classes.</li>
</ol>
<p><em>Definition</em>:-<br />
For a vertex <span class="math-container">$v$</span> of <span class="math-container">$G$</span>, the closed neighborhood of <span class="math-container">$G$</span>, denoted by <span class="math-container">$N[v]$</span>, is <span class="math-container">$v$</span> together with its set of neighbors.<br />
i.e., <span class="math-container">$N[v]=\{v\}\cup\{u : uv\in E(G)\}$</span>.</p>

<graph-theory><graph-colouring>
Coloring where all colors are present in closed neighborhood of every vertex
Cyriac Antony
# Coloring where all colors are present in closed neighborhood of every vertex

(Asked by: username_0 on 2020-11-13)

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)\}$.

**Tags:** graph-theory, graph-colouring

---

## 2 answers

### Answer by username_0 on 2020-11-14. Score: 2 | Accepted answer

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](https://zbmath.org/?q=an:0962.05020).

> **Comments:**
> **username_0**: Another name used in the literature is frozen coloring.  

---

### Answer by username_1 on 2020-11-13. Score: 3

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](https://arxiv.org/abs/1009.6144)

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](https://arxiv.org/abs/2003.05637)

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


---

