Maximum order of (c,s)-normal graphs
Problem 1 · arXiv:1601.01129
Status open high confidence
Problem 1 asks for the exact asymptotics of N(c,s), the maximum number of vertices in a (c,s)-normal graph. The source paper proves N(c,s) ≤ 2^(c+s) and a lower bound of roughly √5^c for N(c,c), but the authors describe these bounds as 'far from conclusive' and explicitly compare the open question to unsolved problems in Ramsey theory. No follow-up paper resolving or substantially improving these bounds was found in a search of the published literature through May 2026.
Reviewer notes. No follow-up found. The paper was published in Combinatorica 38 (2018), 1415–1436 (DOI 10.1007/s00493-017-3559-2). The authors themselves frame the open question as analogous to Ramsey-type problems, suggesting it is expected to be hard. Semantic Scholar and Mohar's publication page returned no relevant citing work on the N(c,s) extremal question specifically.
Context
The authors define $N(c,s)$ as the maximum number of vertices of a $(c,s)$-normal graph, where a graph is $(c,s)$-normal if it admits a normal cover with cliques of sizes at most $c$ and stable sets of sizes at most $s$. They prove $N(c,s) \leq 2^{c+s}$ and a lower bound of roughly $\sqrt{5}^{\,c}$ for $N(c,c)$, but describe the results as 'far from conclusive,' with the exact asymptotics analogous to open questions in Ramsey theory.
Source paper
Minimal normal graph covers
David Gajser, Bojan Mohar · 2016-01-06
https://arxiv.org/abs/1601.01129
PDF source