Chromatic Number of Common Graphs

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.

For a finite simple graph $H$ with $h$ vertices and $e$ edges, let $N_H(G)$ count injective maps $V(H)\to V(G)$ that send edges to edges; nonedges need not be preserved. Call $H$ common if for every sequence of simple graphs $G_j$ with $n_j=|V(G_j)|\to\infty$, \[\liminf_{j\to\infty}\frac{N_H(G_j)+N_H(\overline{G_j})}{n_j^h}\ge 2^{1-e}.\] Here $\overline G$ is the complement, and $\chi(H)$ is the least number of colors in a proper vertex coloring. The constant is the asymptotic value in an independent random two-coloring of the complete graph.

Statement recorded in the supplied source.

Is there an absolute integer $B$ such that every common graph $H$ satisfies $\chi(H)\le B$? [S2]

Short English statement

Are the chromatic numbers of common graphs bounded by a universal constant?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3135 (OPG-59952). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Chromatic Number of Common Graphs, original node 59952, statement and mathematical discussion. https://www.openproblemgarden.org/op/chromatic_number_of_common_graphs.