2
$\begingroup$

Given a simple graph $G=(V,E)$, we use $A_k$ to denote the vertex set of a maximum $k$-colorable subgraph in $G$ when $k\ge 1$, and $A_0=0$.

Will the sequence $|A_1|-|A_0|,|A_2|-|A_1|,\cdots,|A_{\chi(G)}|-|A_{\chi(G)-1}|$ be a non-increasing sequence, where $\chi(G)$ denotes the chromatic number of graph $G$?

$\endgroup$
2
$\begingroup$

Answer. No, this sequence will not always be non-increasing. A counterexample is given in

[AB1980] Michael O. Albertson, David M. Berman, The Chromatic Difference Sequence of a Graph, Journal of Combinatorial Theory, Series B 29, 1-12 (1980)

on page 2, where one finds the following counterexample:

enter image description here

Remarks.

  • If you prefer to have an example which does not make essential use of the somewhat degenerate numbers $\lvert A_1$ and $\lvert A_0\rvert$, which have little to do with coloring, then have a look at page 8 of [AB1980]; there, a rather complicated construction of a graph is given whose chromatic-difference-sequence is $(\lvert A_1\rvert-\lvert A_0\rvert,\lvert A_2\rvert-\lvert A_1\rvert,\lvert A_3\rvert-\lvert A_2\rvert,\lvert A_4\rvert-\lvert A_3\rvert)=(4,4,1,3)$, and the non-monotone subsequence with which that sequence ends is, I would argue, a non-trivial counterexample.

  • [AB1980] also give a (rather unbelievable, though apparently unrefuted) conjecture about how to characterize sequences of the kind you are asking about. (I say "unbelievable" because in view of what is known from complexity theory about the complicatedness of the chromatic-number-function, and about the set of all $k$-colorings, it seems incredible that a class of sequences as intimately bound up with the chromatic number should be humanly understandable).

$\endgroup$

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.