By a coloring of a graph $G = (V,E)$ I mean a map $\kappa:V\to\mathbb{N}$ such that $\kappa(u)\ne \kappa(v)$ whenever $u$ and $v$ are adjacent. (Sometimes this is called a proper coloring but I am not interested in any other kind of coloring.)

By the shape of a coloring I mean the sequence $\lambda_1, \lambda_2, \lambda_3,\ldots$ where $\lambda_i$ is the number of times that the $i$th most popular color is used in the coloring. For example, to say that the shape of a coloring is 5,2,1,1 means that some color was used 5 times, some other color was used 2 times, and two other colors were used 1 time each.

If $\lambda = (\lambda_1, \lambda_2, \lambda_3, \ldots)$ and $\mu = (\mu_1, \mu_2, \mu_3, \ldots)$ are two sequences, I say that $\mu$ majorizes (or dominates) $\lambda$ (written $\mu \ge \lambda$) if $$\sum_{i=1}^k \mu_i \ge \sum_{i=1}^k \lambda_i \qquad \mbox{for all $k$.}$$

Question 1. Is there a term for a coloring whose shape majorizes the shape of every other coloring? Alternatively, is there a term for a graph that admits such a coloring?

It seems that this concept must have been studied before but I have had a hard time searching for the relevant literature. For example, searching for the term "chromatic difference sequence" turns up related papers but nothing spot on. The Greene–Kleitman theorem also seems to be in the right general vicinity but the property I'm interested in is not satisfied by all incomparability graphs. I think I recall seeing the term "completely saturated" somewhere for a closely related (if not identical) concept, but I can't seem to relocate the reference.

Question 2. What examples are there of graphs that admit this sort of coloring?

I recently managed to prove that indifference graphs have this property, and that in fact the First Fit coloring algorithm yields the desired coloring. It feels like I must have rediscovered a known fact, but again, I'm having trouble with my literature search.

(By the way, it's an old question of mine whether the following graphs have the property I'm interested in: Take the vertices of $G$ to be the dots in a Ferrers diagram and declare two vertices to be adjacent if they lie in the same row or column. Back when I first formulated this question, I also spent some time looking for the right literature, with limited success.)

  • $\begingroup$ Does a graph without any edges not admit $(|V|,0,0,\ldots)$ which majorizes any other coloring? I'm missing something it seems. $\endgroup$ – Suvrit Nov 14 '15 at 2:13
  • $\begingroup$ @Suvrit : Yes, a graph without any edges is an example; it happens to be an indifference graph. My question isn't whether there exist examples, but whether there are interesting classes of graphs that are known to have the property. The fact that in my own research I've stumbled across two interesting classes (one still conjectural) makes me feel that this ought to be familiar territory to someone already. $\endgroup$ – Timothy Chow Nov 14 '15 at 2:57
  • 1
    $\begingroup$ You might be interested in the chromatic symmetric functions, defined by Stanley. www-math.mit.edu/~rstan/transparencies/3plus1.pdf I think your question can be phrased very naturally in this context. $\endgroup$ – Per Alexandersson Nov 14 '15 at 3:20
  • 1
    $\begingroup$ I guess complete multipartite graphs have that property, but aren't too interesting. $\endgroup$ – Brendan McKay Nov 14 '15 at 9:48
  • $\begingroup$ @PerAlexandersson : Indeed, I am extremely interested in the chromatic symmetric function, and thinking about it was what led me to prove the result on indifference graphs! Unfortunately, the literature on the chromatic symmetric function does not seem to address either of my questions here. $\endgroup$ – Timothy Chow Nov 15 '15 at 20:49

I managed to find the paper where I encountered the term "completely saturated": Jerrold R. Griggs, "Problems on chain partitions," Discrete Math. 72 (1988), 157–162. If I've chased through all the definitions correctly, another class of graphs with the desired property are incomparability graphs of so-called symmetric chain orders. These are graded posets that can be partitioned into chains each of which skips no ranks between its least and greatest elements and whose ranks are symmetric about the middle. Boolean algebras are the most famous example and a MathSciNet search for "symmetric chain order" yields many others.

Regarding indifference graphs, a couple of people I asked suggested that the result may be implicit if not explicit in the literature on the sum coloring problem. In particular, it may be implicit in the paper by S. Nicoloso, M. Sarrafzadeh, and X. Song, "On the sum coloring problem on interval graphs," Algorithmica 23 (1999), 109–126, which gives an algorithm for sum coloring on interval graphs and derives a corollary about unit interval graphs, but there are a lot of definitions to unwind.

As for terminology, there doesn't seem to be a standard term. If I get enough results to write up and need to coin a term, I might use "dominant coloring" / "dominantly colorable."


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.