Example of graph with strange property

I've also posted this problem in Math Stack Exchange (here).

Note: Whenever I mention a coloring of a graph I'm referring to a proper coloring over its vertices using the least amount of colors.

Pondering on graph coloring I came across a strange class $$\mathcal G$$ of problematic graphs. A graph $$G$$ is in $$\mathcal G$$ if it has the following property:

For any vertex $$v$$, any coloring $$c$$ of $$G$$ and any color $$\alpha\in c[N(v)]$$ there is a coloring $$k$$ of $$G$$ such that

• There is no vertex $$u\neq v$$ such that $$k(u) = k(v)$$
• $$k^{-1}[\alpha]\cap N(v) = c^{-1}[\alpha]\cap N(v)$$

That is, given a coloring, we can always find another one that preserves a chosen color in the neighborhood of a chosen vertex while making the color of this vertex unique in the graph.

The thing is: I don't know any graph with this property, except by the complete ones. It's easy to show that, if such a graph has chromatic number one, two or three, then it must be complete. Is it also true for higher chromatic numbers? Can you give me an example of a graph in this class that is not complete?

One possible strategy to approach this problem is trying to determine properties of such graphs (to hopefully prove they must be complete or filter searches for an example). It's not very hard to see that, if $$G$$ is in $$\mathcal G$$

• and $$v$$ is a vertex of $$G$$, then $$\chi(G-v) = \chi(G)-1$$.
• and $$e$$ is an edge of $$G$$, then $$\chi(G-e) = \chi(G)-1$$.

that is, $$G$$ is vertex and edge minimal. Those seem to be the most natural properties to find.

As pointed out in a comment, it is also possible to show that, if $$\chi(G)>2$$, then each vertex of $$G$$ belongs to a triangle. This result can be extended: given a vertex $$v$$ of $$G$$, there can not be a set of more than $$\deg(v)-\chi(G)+2$$ independent vertices in $$N(v)$$.

Upon closer inspection, I realized the interesting class of problematic graphs is actually (probably) narrower than I previously thought. Let's call it $$\mathcal H$$. A graph $$G$$ is in $$\mathcal H$$ if it has the following property:

For any vertex $$v$$ and any nonempty set $$S\subset N(v)$$ of independent vertices there is a coloring $$c$$ of $$G$$ such that

• There is no vertex $$u\neq v$$ such that $$c(u) = c(v)$$
• $$S = c^{-1}[\alpha]\cap N(v)$$ for some color $$\alpha$$

It's clear that $$\mathcal H\subset \mathcal G$$, so the previously mentioned properties must still apply. It's not clear if $$\mathcal H\neq \mathcal G$$. However, I'm only interested in knowing if there is a non-complete graph in $$\mathcal H$$.

• If $G\in\mathcal G$ and $\chi(G)\gt2$ then each vertex of $G$ belongs to a triangle.
– bof
Commented Apr 29, 2023 at 20:35
• Oh, I see, that already follows from vertex minimality. Commented May 3, 2023 at 7:21
• @LouisD Such graphs are exactly the vertex-critical graphs (your property is equivalent to saying that for all vertices $v$, the chromatic number of $G-v$ is one less than the chromatic number of $v$.) An easy class of examples with chromatic number $k\ge 3$ is obtained by starting with an odd cycle and adding $k-3$ new vertices adjacent to every vertex of the cycle and to each other. Commented May 3, 2023 at 22:03
• Surely, in the last set up, you mean that this holds for every nomnempty set $S$? Commented Sep 14, 2023 at 9:01
• @IlyaBogdanov surely! Thank you for pointing it out. Commented Sep 15, 2023 at 4:09