χ_ISC strict inequality for non-complete graphs

Conjecture 1.1 · arXiv:1703.05380

arXiv Conjecture high confidence— first stated 2021-01-06

Authors: Marthe Bonamy, Kitty Meeks

Status open high confidence

No follow-up paper resolving Conjecture 1.1 from arXiv:1703.05380 was found in the indexed literature. The conjecture remains open as of May 2026; the source paper itself provides evidence by confirming it for sc-greedy graphs, trees, unbalanced complete bipartite graphs, and grids, but the general statement is unproved.

Reviewer notes. No follow-up found after four web searches and one WebFetch. The conjecture was published in Discrete Applied Mathematics (January 2021). Semantic Scholar page returned no content. The conjecture is niche enough that absence of indexed follow-up after ~5 years is consistent with it being genuinely open.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. If any connected component of $G$ is not a complete graph, then $\chi_{ISC}(G) < \chi_{SC}(G)$.

Context

The authors show that the interactive sum choice number satisfies $\chi_{ISC}(G) \leq \chi_{SC}(G)$ for all graphs $G$, and that equality holds when $G$ is a disjoint union of complete graphs (since Bob can force every vertex to receive colours $1, 2, \ldots$ in order). They believe this is the only case of equality, motivating the conjecture. The paper provides evidence by confirming it for sc-greedy graphs, trees, unbalanced complete bipartite graphs, and grids.

Notes. Source is PDF; the conjecture statement itself contains only simple inequality notation and is cleanly readable.

Source paper

The Interactive Sum Choice Number of Graphs
Marthe Bonamy, Kitty Meeks · 2021-01-06
https://arxiv.org/abs/1703.05380 PDF source