# Graphs with a coloring that majorizes all other colorings

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.)

• Does a graph without any edges not admit $(|V|,0,0,\ldots)$ which majorizes any other coloring? I'm missing something it seems. Nov 14, 2015 at 2:13
• @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. Nov 14, 2015 at 2:57
• 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. Nov 14, 2015 at 3:20
• I guess complete multipartite graphs have that property, but aren't too interesting. Nov 14, 2015 at 9:48
• @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. Nov 15, 2015 at 20:49