Given positive integers $d \ge 3$, $r>2$ and $l$, with $2d \le l <rd$. Every vertice of the graph $G(V,E)$ is assigned to a positive integer in $\{1,2,\cdots,l\}$, such that for any two consecutive vertices in the graph, the integers they are assigned to, respectively, have difference no less than $d$, and no more than $l-d$. A proper coloring of the graph is a coloring of the vertices, such that any two consecutive vertices are not the same color. It's given that there exist a proper subset $A$ of $V$, such that for $G$'s any proper coloring with $r-1$ colors, and for an arbitrary color $C$, either all numbers in color $C$ appear in $A$, or none of the numbers in color $C$ appear in $A$. Show that $G$ has a proper coloring within $r-1$ colors.
Problem
Source: 2019 China TST Test 3 P6
Tags: combinatorics, graph theory
stroller
13.04.2019 04:33
Bump $ $
61plus
14.04.2019 16:55
I believe the first $r-1$ should be $r$. Note that the condition of difference no less than $d$, and no more than $l-d$ just means that the numbers are at least $d$ apart, where we work over$\pmod{l}$ whenever labels are concerned. We assume that there is a counterexample. Lemma 1: An $r$ coloring exists.
The chromatic number is generally a very difficult problem so we suspect that the labeling is central in determining the coloring.
The set of vertices with labels from the following set $\lbrace x,x+1,\ldots,x+k\rbrace$, where $k<d$, are all disjoint, and hence can be assigned one color.
Now this means that if we have $l=md+s, m\leq r-1, 0\leq s<d$, we can just separate the vertices into sets of
\begin{align*}
&\lbrace cd+1, cd+2, \ldots, (c+1)d\rbrace,& 0\leq c \leq m-1\\
&\lbrace md+1,md+2,\ldots,md+s\rbrace ,& \text{if } s\neq 0\\
\end{align*}and color them with one color each. At most $m+1$ colors are used, and if $m<r-1$, or $m=r-1,s=0$ we are done. So let $m=r-1,s>0$ .
Claim 1: The distance between two consecutive used labels is $\leq d-1$, given that there is no $r-1$ coloring.
From the proof of the first claim, we suspect that we can do better to optimize the coloring, since we only worry about labels that are used.
Suppose we are looking at a label $x$ that is used, and the label directly before it that is used is at least $d$ away (so it is $\leq x-d$ ). Then WLOG $1$ is the label (subtract $x-1$ from every label) and we get that there are no vertices with labels $$\{(r-1)d+1,(r-1)d+2,\ldots,(r-1)d+s\}.$$We do not actually need the last color, and $r-1$ colors will suffice. Thus we are left we the case where the distance between two consecutive used labels is $\leq d-1$.
Claim 2: The second condition forbids that the distance between two consecutive used labels is always $\leq d-1$.
The set $C$ must contain every vertex of label $x$, if it contains at least one vertex labelled $x$, according to our initial coloring in Lemma 1. We can alter the first coloring by adding $x-1$ everywhere, then every vertex labelled $y$ satisfying $x< y\leq x+d-1$ is also of the same color and must also be in $C$. There is at least one such label from what we have previously. Now use this as the new $x$, and eventually we get that every vertex must be in $C$.
Claim 1 and 2 cannot hold simultaneously, so we have a contradiction.