# Example of graph with strange property

The question is now also published in MathOverflow (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 improved: 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 then 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$$.

• $c'(v)\neq c'(u)$ for all $u$ vertex of $G$, $u\neq v$ this seems to be saying every vertex has its own colour in $c'$ Commented Mar 16, 2023 at 17:26
• The vertex $v$ is fixed. Commented Mar 16, 2023 at 17:52
• When you say a coloring is minimal, do you mean that every color is taken by some vertex or further that any two colors have vertices that are neighbors? Commented Apr 24, 2023 at 7:18
• @ronno a proper minimal coloring is a proper coloring that uses the least amount of colors. I think that is equivalent to say that any two colors have vertices that are neighbors. Commented Apr 24, 2023 at 16:01
• @AlmaArjuna Those are not equivalent. E.g. we can take a graph that's a matching on $\binom k2$ edges and then $k$-color it by finding an edge for each pair of colors, but obviously a matching can also be $2$-colored. Commented Apr 27, 2023 at 2:46