Independent sets in n-vertex k-chromatic ℓ-connected graphs

NEW

Problem: For finite simple graphs, $i_t(G)$ denotes the number of independent sets of size $t$. For $k\le \ell$, the paper defines

Conjecture 5.3 asserts: if $3\le k\le \ell$, $n\ge 2\ell$, $G$ is an $n$-vertex $k$-chromatic $\ell$-connected graph, and $t\ge3$, then

Result: The conjecture is false.

Take

and let

Thus $G$ is the join of two disjoint 5-vertex graphs, each consisting of one edge and three isolated vertices.

First, $G$ is $4$-chromatic. Each copy of $K_2\cup E_3$ needs two colors, and because every vertex in one copy is adjacent to every vertex in the other, the two copies must use disjoint color sets. Hence

Second, $G$ is $5$-connected. Deleting fewer than $5$ vertices leaves at least one vertex in each of the two 5-vertex sides. Since all cross-edges between the two sides are present, the remaining graph is connected. Deleting all vertices of one side leaves $K_2\cup E_3$, which is disconnected, so the connectivity is exactly $5$.

Now count independent triples. Since the join has all cross-edges, every independent set lies entirely in one side. In one copy of $K_2\cup E_3$, an independent triple is either the three isolated vertices, or one endpoint of the $K_2$ together with two of the three isolated vertices. Thus one side contributes

independent triples, so

But for these parameters,

Its independent triples are either chosen from the $E_5$, giving $\binom53=10$, or from $K_3\cup E_2$, where one chooses one vertex of $K_3$ and both vertices of $E_2$, giving $3$. Therefore

Hence

contradicting Conjecture 5.3.

Citation: Conjecture and notation: Engbers, Keough, Short, “Independent Sets in $n$-vertex $k$-chromatic, $\ell$-connected graphs,” arXiv:1907.03913, Conjecture 5.3. No external counterexample citation used.