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.

complement-compatible $k$-coloring? Or perhaps: a Jenča-coloring! :-) – Joseph O'Rourke Oct 14 '11 at 23:48maximally $k$-colored. – Joseph O'Rourke Oct 15 '11 at 23:54Mathematics Magazine, Vol. 66, No. 4 (Oct., 1993), pp. 211-226): you want to color a map where some of the countries consist of disjoint regions, but each country must be assigned a single color. An "m-pire" is a country consisting of m disjoint regions. So we could call the $P_{k}$ property "k-colorable with one 2-pire". – Doug Chatham Oct 16 '11 at 12:30edge-maximal $k$-colourable. This property can be useful in induction on the number ofnon-edgesin a graph. – Andrew D. King Oct 17 '11 at 21:10