Exact values of the cover numbers by perfect, generalized split, co-unipolar and unipolar graphs, and which functions are cover-number functions

Marits (Discrete Applied Mathematics 379 (2026) 400–404) proved that the cover number of a graph $G$ by any class of the form $\{\chi\le f(\omega)\}$, for non-decreasing $f$ majorizing the identity, equals $\lceil\log\chi(G)/\log f(\omega(G))\rceil$ and established a five-term chain of cover numbers — by the class $\{\chi=\omega\}$, by perfect graphs, by generalized split graphs, by co-unipolar graphs and by bipartite graphs — in which every gap is unbounded; the cover number by unipolar graphs was further shown not to be a function of the chromatic and clique numbers, since the hypercubes $Q_d$ have $\chi=\omega=2$ but unipolar cover number $d$. The paper's closing section leaves three problems open: exact values or tight parameter-based characterizations of the cover numbers by perfect, generalized split and co-unipolar graphs; an exact formula for the unipolar cover number via graph parameters other than $\chi$ and $\omega$; and a characterization of which functions from graphs to natural numbers arise as the cover-number function of some graph class.

Background

For a graph class $\mathcal{P}$, a covering of a graph $G$ by $\mathcal{P}$-graphs is an expression of the edge set as a union $E(G)=E(G_1)\cup\cdots\cup E(G_k)$ with each $G_i$ in $\mathcal{P}$, and the cover number $c_{\mathcal{P}}(G)$ is the smallest such $k$. The classical instance is the biparticity of a graph — the cover number by bipartite graphs, i.e. graphs whose vertex set splits into two independent sets — for which Harary, Hsu and Miller (1977) proved the exact formula $c_{\mathbf{BIP}}(G)=\lceil\log_2\chi(G)\rceil$, where $\chi(G)$ is the chromatic number, the minimum number of independent color classes needed to color the vertices.

Marits (2026) extended this formula to every chromatic-bounded class. A graph class is $\chi$-bounded with binding function $f$ if every graph $G$ in it satisfies $\chi(G)\le f(\omega(G))$, where $\omega(G)$ is the clique number, the size of a largest complete subgraph; for every non-decreasing $f$ majorizing the identity, Marits proved $c_{\{\chi\le f(\omega)\}}(G)=\lceil\log\chi(G)/\log f(\omega(G))\rceil$ (logarithms in base 2). This closes the covering question for all classes controlled by chromatic number alone.

The natural classes still missing from this picture live in the perfect-graph world. A graph is perfect if every induced subgraph $H$ satisfies $\chi(H)=\omega(H)$; by the Strong Perfect Graph Theorem of Chudnovsky, Robertson, Seymour and Thomas (2006), these are exactly the graphs containing no odd hole (induced cycle on at least five vertices) and no odd antihole (the complement of one). A graph is unipolar if its vertex set partitions into one clique $A$ and a disjoint union of cliques $B$, with arbitrary edges between $A$ and $B$; it is co-unipolar if its complement is unipolar, equivalently if its vertex set partitions into an independent set and a set inducing a complete multipartite graph, with arbitrary edges between the two parts; and it is generalized split (GSP) if it is unipolar or co-unipolar. All generalized split graphs are perfect (McDiarmid and Yolov 2015), and a counting result of Prömel and Steger (1992), combined with the Strong Perfect Graph Theorem, shows that 'almost all' perfect graphs are generalized split. Since $\mathbf{BIP}\subseteq\mathbf{coUNIP}\subseteq\mathbf{GSP}\subseteq\mathbf{PERF}\subseteq\{\chi=\omega\}$ and the cover number is monotone under class inclusion, one obtains the chain $c_{\{\chi=\omega\}}=\left\lceil\frac{\log\chi}{\log\omega}\right\rceil\le c_{\mathbf{PERF}}\le c_{\mathbf{GSP}}\le c_{\mathbf{coUNIP}}\le c_{\mathbf{BIP}}=\lceil\log\chi\rceil.$ Marits proved that at every single inequality of this chain the gap between the two sides can grow arbitrarily large, so no exact formula for the middle terms can be read off from the endpoints. The unipolar cover number $c_{\mathbf{UNIP}}$ does not even sit in the chain, because unipolar graphs do not contain all bipartite graphs; Marits proved that $c_{\mathbf{UNIP}}$ is not bounded by any function of $\chi$ and $\omega$ together, using the hypercube graphs $Q_d$ (the graphs on vertex set $\{0,1\}^d$ joining vertices that differ in exactly one coordinate), which satisfy $\chi(Q_d)=\omega(Q_d)=2$ yet $c_{\mathbf{UNIP}}(Q_d)=d$ for all $d\ge 8$. Against this backdrop, the paper poses the three open problems studied here.

Problem Statement

These are the three open problems posed in Section 3 of Marits, 'Cover numbers by certain graph families' (Discrete Applied Mathematics 379 (2026) 400–404). Throughout, for a graph class $\mathcal{P}$, the cover number $c_{\mathcal{P}}(G)$ is the minimum number of $\mathcal{P}$-graphs whose edge sets cover $E(G)$; the union in a covering is exact, so every covering graph is a subgraph of $G$, and its pieces may overlap on edges. The classes involved: the perfect graphs are those whose every induced subgraph $H$ satisfies $\chi(H)=\omega(H)$, where $\chi$ is the chromatic number and $\omega$ the clique number; a graph is unipolar if its vertex set partitions into one clique and a disjoint union of cliques, with arbitrary edges between the two parts; co-unipolar if its complement is unipolar; and generalized split (GSP) if it is unipolar or co-unipolar.

(1) Determine the exact value of the cover numbers by perfect graphs ($c_{\mathbf{PERF}}$), by co-unipolar graphs ($c_{\mathbf{coUNIP}}$) and by generalized split graphs ($c_{\mathbf{GSP}}$): either an explicit formula in terms of the chromatic number, if one exists, or a tight characterization via other graph parameters, replacing the inequalities $c_{\{\chi=\omega\}}\le c_{\mathbf{PERF}}\le c_{\mathbf{GSP}}\le c_{\mathbf{coUNIP}}\le c_{\mathbf{BIP}}$ by exact statements identifying the governing parameters.

(2) Determine the exact value of the cover number by unipolar graphs, $c_{\mathbf{UNIP}}$. It is known that $c_{\mathbf{UNIP}}$ is unbounded as a function of the chromatic number (indeed of $\chi$ and $\omega$ together), so the question is whether a formula using different graph parameters is still attainable, and if so, through which parameters.

(3) Realizability of cover-number functions: given a function $f$ assigning a natural number to each graph, decide whether there exists a graph class $\mathcal{P}$ with $c_{\mathcal{P}}(G)=f(G)$ for all graphs $G$; equivalently, characterize exactly which functions arise as the cover-number function of some graph class.

The common objective is the exact determination of cover numbers along the perfect-graph chain and a complete description of the range of the construction $\mathcal{P}\mapsto c_{\mathcal{P}}$: every answer must hold for all graphs, not for a restricted family.

References

1. Márton Marits (2026), 'Cover numbers by certain graph families', Discrete Applied Mathematics 379:400–404, DOI 10.1016/j.dam.2025.09.009, https://doi.org/10.1016/j.dam.2025.09.009 (preprint arXiv:2412.08980, https://arxiv.org/abs/2412.08980)
2. Anna Gujgiczer, Márton Marits, Kenta Ozeki (2026), 'Cover numbers by graph families bounded by certain graph parameters', arXiv:2607.12353, https://arxiv.org/abs/2607.12353
3. Benny George Kenkireth, Gopalan Sajith, Sreyas Sasidharan (2025), 'Word-representability and comparability: Minimal forbidden induced subgraphs and cover number bounds', arXiv:2502.06979 (v4, June 2026), https://arxiv.org/abs/2502.06979
4. András Gyárfás, Márton Marits, Géza Tóth (2024), 'Partitioning perfect graphs into comparability graphs', arXiv:2408.13523 (v2, March 2026), https://arxiv.org/abs/2408.13523
5. Frank Harary, D. Hsu, Zevi Miller (1977), 'The biparticity of a graph', Journal of Graph Theory 1(2):131–133, DOI 10.1002/jgt.3190010208, https://doi.org/10.1002/jgt.3190010208
6. Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas (2006), 'The strong perfect graph theorem', Annals of Mathematics 164:51–229, DOI 10.4007/annals.2006.164.51, https://doi.org/10.4007/annals.2006.164.51
7. Colin McDiarmid, Nikola Yolov (2015), 'Recognition of unipolar and generalised split graphs', Algorithms 8(1):46–59, DOI 10.3390/a8010046 (preprint arXiv:1604.00922), https://doi.org/10.3390/a8010046
8. Hans Jürgen Prömel, Angelika Steger (1992), 'Almost all Berge graphs are perfect', Combinatorics, Probability and Computing 1(1):53–79, DOI 10.1017/S0963548300000079, https://doi.org/10.1017/S0963548300000079
9. Miriam Goetze, Lucas Schwebler (2026), 'On the computational complexity of local and global covering numbers', arXiv:2607.18833, https://arxiv.org/abs/2607.18833
10. Miriam Goetze, Peter Stumpf, Torsten Ueckerdt (2025), 'Boundedness and separation in the graph covering number framework', arXiv:2504.17458, https://arxiv.org/abs/2504.17458
11. Pierre Aboulker, Logan Crew, Julien Duron, Xinyue Fan, Hugo Jacob, Rémy Kimbrough, Hidde Koerts, Benjamin Moore, Sophie Spirkl, Stéphan Thomassé (2026), 'Decomposing tournaments into comparability graphs', arXiv:2606.07748, https://arxiv.org/abs/2606.07748