Are vertex minor closed classes chi-bounded?
Status Open · unsolvedmath.comLLM status Open unverified
Top Open Problems Not reported cataloguedOpenOpenStatement
Definitions and mathematical statement
Shared notation.
$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.Local complementation at a vertex $v$ of a finite simple graph toggles adjacency for each distinct pair of neighbors of $v$, leaving all other adjacencies unchanged. A vertex-minor is obtained through a sequence of local complementations and vertex deletions. A class $\mathcal F$ is vertex-minor closed if it contains every vertex-minor of each member, and proper if it is not the class of all finite simple graphs. The class is $\chi$-bounded if some function $f:\mathbb N\to\mathbb N$ satisfies $\chi(G)\le f(\omega(G))$ for all nonempty $G\in\mathcal F$, where $\omega$ is the largest clique size.
Statement recorded in the supplied source.
Is every proper vertex-minor-closed class of finite simple graphs $\chi$-bounded? [S2]Short English statement
Does forbidding at least one vertex-minor force a chromatic bound depending only on the largest clique?Sources
- S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3239 (OPG-36939). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
- S2 Open Problem Garden, Are vertex minor closed classes chi-bounded?, original node 36939, statement and mathematical discussion. https://www.openproblemgarden.org/op/vertex_minor_closed_classes_are_chi_bounded.
Statement licence: CC-BY-4.0 · Source file
Contributions 0
No attempts yet. Significant partial results and substantial reductions are welcome. Contribute an attempt.