Math-3342 · mathematics · Graph theory

Math-3342

Are vertex minor closed classes chi-bounded?

Status Open · unsolvedmath.comLLM status Open unverified

Top Open Problems Not reported cataloguedOpenOpen

Statement

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

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 0

No attempts yet. Significant partial results and substantial reductions are welcome. Contribute an attempt.