7
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I think you can make up your own name for it! A complement-compatible $k$-coloring? Or perhaps: a Jenča-coloring! :-) $\endgroup$
    – Joseph O'Rourke
    Oct 14, 2011 at 23:48
  • $\begingroup$ @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?". $\endgroup$
    – Gejza Jenča
    Oct 15, 2011 at 8:24
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joseph O'Rourke
    Oct 15, 2011 at 23:54
  • 1
    $\begingroup$ This reminds me of the m-pire (or empire) problem (see mathworld.wolfram.com/EmpireProblem.html 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". $\endgroup$
    – Doug Chatham
    Oct 16, 2011 at 12:30
  • 1
    $\begingroup$ 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. $\endgroup$
    – Andrew D. King
    Oct 17, 2011 at 21:10

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.