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$.
