The following property emerged naturally when I was playing with certain generalizations of Kneser graphs.
Let $k>0$ be a natural number. Consider a property $P_k$ of graphs defined as follows.
For every non-edge $(u,v)$ there is a $k$-coloring such that $u$ and $v$ have the same color.
It is clear that every $k-1$-colorable graph has the $P_k$ property -- we can use the spare color for the non-edge and leave the other colors as they are.
Not every $k$-colorable graph has the $P_k$ property: $C_6$ is 2-colorable, but has not the $P_2$ property.
What is this property called?
EDIT: Some additional observations from last night.
- If some $k$-colorable graph $G$ has not the $P_k$ property, then there is a non-edge $(u,v)$ in $G$ such that for every $k$-coloring of $G$ the colors of $u$ and $v$ are distinct. That means that every $k$-coloring of $G$ is a $k$-coloring of $G\cup(u,v)$.
- Thus a graph $G$ has not the $P_k$ property iff we can add an edge with no effect on $k$-colorings and
- $P_k$ property means that you cannot add an edge without losing some of the $k$-colorings.
- So any $k$-colorable graph can be embedded into a graph with the $P_k$ property.
- For example, if we start with $C_6$ we can add step-by-step 3 edges without any effect on 2-colorings; the resulting graph
has the $P_2$ property.