MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
I think you can make up your own name for it! A complement-compatible $k$-coloring? Or perhaps: a Jenča-coloring! :-) – Joseph O'Rourke Oct 14 '11 at 23:48
@Joseph O'Rourke: Well, yes. I understand that as a subtle reminder that I should ask a slightly different question; something like "Has anyone seen anything like this before?". – Gejza Jenča Oct 15 '11 at 8:24
I meant nothing so subtle: I only meant that, since no one has recognized it so far, it seems free for you to name it. Your characterization, "you cannot add an edge without losing some of the $k$-colorings," suggests: maximally $k$-colored. – Joseph O'Rourke Oct 15 '11 at 23:54
This reminds me of the m-pire (or empire) problem (see or Coloring Ordinary Maps, Maps of Empires, and Maps of the Moon, Joan P. Hutchinson, Mathematics 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:30
I would call such a graph edge-maximal $k$-colourable. This property can be useful in induction on the number of non-edges in a graph. – Andrew D. King Oct 17 '11 at 21:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.