Problem 1872

We will prove the following more general statement.

Claim. Let $G$ be a graph with chromatic number $k \geqslant 3$. Then $G$ contains at least $2^{k-1}-k$ unsociable groups.

Recall that the chromatic number of $G$ is the least $k$ such that a proper coloring
$$V=V_{1} \sqcup \cdots \sqcup V_{k}$$
exists. In view of $2^{11}-12>2015$, the claim implies the problem statement.

Let $G$ be a graph with chromatic number $k$. We say that a proper coloring (1) of $G$ is leximinimal, if the $k$-tuple $( |V_{1}|,|V_{2}|, \ldots,|V_{k}| )$ is lexicographically minimal; in other words, the following conditions are satisfied: the number $n_{1}=|V_{1}|$ is minimal; the number $n_{2}=|V_{2}|$ is minimal, subject to the previously chosen value of $n_{1}$; $\ldots$; the number $n_{k-1}=|V_{k-1}|$ is minimal, subject to the previously chosen values of $n_{1}, \ldots, n_{k-2}$.

The following lemma is the core of the proof.

Lemma 1. Suppose that $G=(V, E)$ is a graph with odd chromatic number $k \geqslant 3$, and let (1) be one of its leximinimal colorings. Then $G$ contains an odd cycle which visits all color classes $V_{1}, V_{2}, \ldots, V_{k}$.

*Proof of Lemma 1.* Let us call a cycle colorful if it visits all color classes.

Due to the definition of the chromatic number, $V_{1}$ is nonempty. Choose an arbitrary vertex $v \in V_{1}$. We construct a colorful odd cycle that has only one vertex in $V_{1}$, and this vertex is $v$.

We draw a subgraph of $G$ as follows. Place $v$ in the center, and arrange the sets $V_{2}, V_{3}, \ldots, V_{k}$ in counterclockwise circular order around it. For convenience, let $V_{k+1}=V_{2}$. We will draw arrows to add direction to some edges of $G$, and mark the vertices these arrows point to. First we draw arrows from $v$ to all its neighbors in $V_{2}$, and mark all those neighbors. If some vertex $u \in V_{i}$ with $i \in\{2,3, \ldots, k\}$ is already marked, we draw arrows from $u$ to all its neighbors in $V_{i+1}$ which are not marked yet, and we mark all of them. We proceed doing this as long as it is possible. The process of marking is exemplified in Figure 1.

Notice that by the rules of our process, in the final state, marked vertices in $V_{i}$ cannot have unmarked neighbors in $V_{i+1}$. Moreover, $v$ is connected to all marked vertices by directed paths.

Now move each marked vertex to the next color class in circular order (see an example in Figure 3). In view of the arguments above, the obtained coloring $V_{1} \sqcup W_{2} \sqcup \cdots \sqcup W_{k}$ is proper. Notice that $v$ has a neighbor $w \in W_{2}$, because otherwise
$$\left(V_{1} \backslash\{v\}\right) \sqcup\left(W_{2} \cup\{v\}\right) \sqcup W_{3} \sqcup \cdots \sqcup W_{k}$$
would be a proper coloring lexicographically smaller than (1). If $w$ was unmarked, i.e., $w$ was an element of $V_{2}$, then it would be marked at the beginning of the process and thus moved to $V_{3}$, which did not happen. Therefore, $w$ is marked and $w \in V_{k}$.

Figure 1
Figure 2

Since $w$ is marked, there exists a directed path from $v$ to $w$. This path moves through the sets $V_{2}, \ldots, V_{k}$ in circular order, so the number of edges in it is divisible by $k-1$ and thus even. Closing this path by the edge $w \rightarrow v$, we get a colorful odd cycle, as required. $\square$

*Proof of the claim.* Let us choose a leximinimal coloring (1) of $G$. For every set $C \subseteq\{1,2, \ldots, k\}$ such that $|C|$ is odd and greater than $1$, we will provide an odd cycle visiting exactly those color classes whose indices are listed in the set $C$. This property ensures that we have different cycles for different choices of $C$, and it proves the claim because there are $2^{k-1}-k$ choices for the set $C$.

Let $V_{C}=\bigcup_{c \in C} V_{c}$, and let $G_{C}$ be the induced subgraph of $G$ on the vertex set $V_{C}$. We also have the induced coloring of $V_{C}$ with $|C|$ colors; this coloring is of course proper. Notice further that the induced coloring is leximinimal: if we had a lexicographically smaller coloring $\left(W_{c}\right)_{c \in C}$ of $G_{C}$, then these classes, together the original color classes $V_{i}$ for $i \notin C$, would provide a proper coloring which is lexicographically smaller than (1). Hence Lemma 1, applied to the subgraph $G_{C}$ and its leximinimal coloring $\left(V_{c}\right)_{c \in C}$, provides an odd cycle that visits exactly those color classes that are listed in the set $C$. $\square$

We provide a different proof of the claim from the previous solution.

We say that a graph is critical if deleting any vertex from the graph decreases the graph's chromatic number. Obviously every graph contains a critical induced subgraph with the same chromatic number.

Lemma 2. Suppose that $G=(V, E)$ is a critical graph with chromatic number $k \geqslant 3$. Then every vertex $v$ of $G$ is contained in at least $2^{k-2}-1$ unsociable groups.

*Proof.* For every set $X \subseteq V$, denote by $n(X)$ the number of neighbors of $v$ in the set $X$.

Since $G$ is critical, there exists a proper coloring of $G \backslash\{v\}$ with $k-1$ colors, so there exists a proper coloring $V=V_{1} \sqcup V_{2} \sqcup \cdots \sqcup V_{k}$ of $G$ such that $V_{1}=\{v\}$. Among such colorings, take one for which the sequence $\left(n\left(V_{2}\right), n\left(V_{3}\right), \ldots, n\left(V_{k}\right)\right)$ is lexicographically minimal. Clearly, $n\left(V_{i}\right)>0$ for every $i=2,3, \ldots, k$; otherwise $V_{2} \sqcup \ldots \sqcup V_{i-1} \sqcup\left(V_{i} \cup V_{1}\right) \sqcup V_{i+1} \sqcup \ldots V_{k}$ would be a proper coloring of $G$ with $k-1$ colors.

We claim that for every $C \subseteq\{2,3, \ldots, k\}$ with $|C| \geqslant 2$ being even, $G$ contains an unsociable group so that the set of its members' colors is precisely $C \cup\{1\}$. Since the number of such sets $C$ is $2^{k-2}-1$, this proves the lemma. Denote the elements of $C$ by $c_{1}, \ldots, c_{2 \ell}$ in increasing order. For brevity, let $U_{i}=V_{c_{i}}$. Denote by $N_{i}$ the set of neighbors of $v$ in $U_{i}$.

We show that for every $i=1, \ldots, 2 \ell-1$ and $x \in N_{i}$, the subgraph induced by $U_{i} \cup U_{i+1}$ contains a path that connects $x$ with another point in $N_{i+1}$. For the sake of contradiction, suppose that no such path exists. Let $S$ be the set of vertices that lie in the connected component of $x$ in the subgraph induced by $U_{i} \cup U_{i+1}$, and let $P=U_{i} \cap S$, and $Q=U_{i+1} \cap S$ (see Figure 3). Since $x$ is separated from $N_{i+1}$, the sets $Q$ and $N_{i+1}$ are disjoint. So, if we re-color $G$ by replacing $U_{i}$ and $U_{i+1}$ by $\left(U_{i} \cup Q\right) \backslash P$ and $\left(U_{i+1} \cup P\right) \backslash Q$, respectively, we obtain a proper coloring such that $n\left(U_{i}\right)=n\left(V_{c_{i}}\right)$ is decreased and only $n\left(U_{i+1}\right)=n\left(V_{c_{i+1}}\right)$ is increased. That contradicts the lexicographical minimality of $\left(n\left(V_{2}\right), n\left(V_{3}\right), \ldots, n\left(V_{k}\right)\right)$.

Figure 3

Next, we build a path through $U_{1}, U_{2}, \ldots, U_{2 \ell}$ as follows. Let the starting point of the path be an arbitrary vertex $v_{1}$ in the set $N_{1}$. For $i \leqslant 2 \ell-1$, if the vertex $v_{i} \in N_{i}$ is already defined, connect $v_{i}$ to some vertex in $N_{i+1}$ in the subgraph induced by $U_{i} \cup U_{i+1}$, and add these edges to the path. Denote the new endpoint of the path by $v_{i+1}$; by the construction we have $v_{i+1} \in N_{i+1}$ again, so the process can be continued. At the end we have a path that starts at $v_{1} \in N_{1}$ and ends at some $v_{2 \ell} \in N_{2 \ell}$. Moreover, all edges in this path connect vertices in neighboring classes: if a vertex of the path lies in $U_{i}$, then the next vertex lies in $U_{i+1}$ or $U_{i-1}$. Notice that the path is not necessary simple, so take a minimal subpath of it. The minimal subpath is simple and connects the same endpoints $v_{1}$ and $v_{2 \ell}$. The property that every edge steps to a neighboring color class (i.e., from $U_{i}$ to $U_{i+1}$ or $U_{i-1}$ ) is preserved. So the resulting path also visits all of $U_{1}, \ldots, U_{2 \ell}$, and its length must be odd. Closing the path with the edges $v v_{1}$ and $v_{2 \ell} v$ we obtain the desired odd cycle (see Figure 4).

Figure 4

Now we prove the claim by induction on $k \geqslant 3$. The base case $k=3$ holds by applying Lemma 2 to a critical subgraph. For the induction step, let $G_{0}$ be a critical $k$-chromatic subgraph of $G$, and let $v$ be an arbitrary vertex of $G_{0}$. By Lemma 2, $G_{0}$ has at least $2^{k-2}-1$ unsociable groups containing $v$. On the other hand, the graph $G_{0} \backslash\{v\}$ has chromatic number $k-1$, so it contains at least $2^{k-2}-(k-1)$ unsociable groups by the induction hypothesis. Altogether, this gives $2^{k-2}-1+2^{k-2}-(k-1)=2^{k-1}-k$ distinct unsociable groups in $G_{0}$ (and thus in $G$ ).