Is the local bipartite covering number bounded by a function of the fractional chromatic number? (Question 6.1 of Goetze–Schwebler)

The local bipartite covering number $c_{\mathrm{l}}^{\mathcal{B}}(H)$ of a graph $H$ is the smallest $k$ such that the edges of $H$ can be covered by bipartite subgraphs with every vertex of $H$ lying in at most $k$ of the covering subgraphs. Goetze and Schwebler (2026) proved the lower bound $c_{\mathrm{l}}^{\mathcal{B}}(H) \ge \lceil \log_2(\chi_{\mathrm{f}}(H))\rceil$ , where $\chi_{\mathrm{f}}$ is the fractional chromatic number, and asked whether any control holds in the opposite direction: does there exist a function $f$ with $c_{\mathrm{l}}^{\mathcal{B}}(H) \le f(\chi_{\mathrm{f}}(H))$ for every graph $H$ , and, more generally, for each real $r \ge 2$ a function $f_r$ bounding the local covering number by guests of fractional chromatic number at most $r$ ? The source authors conjecture a negative answer. The question is open.

Background

Throughout, graphs are finite, simple and undirected. For a fixed "guest" graph class $\mathcal{G}$ , a $\mathcal{G}$ -cover of a graph $H$ is a collection of subgraphs $G_1,\dots,G_t$ of $H$ , each belonging to $\mathcal{G}$ , whose union contains every edge of $H$ . The global $\mathcal{G}$ -covering number $c_{\mathrm{g}}^{\mathcal{G}}(H)$ is the smallest number of guests in such a cover. The local $\mathcal{G}$ -covering number $c_{\mathrm{l}}^{\mathcal{G}}(H)$ is the smallest $k$ for which $H$ has a $\mathcal{G}$ -cover in which every vertex of $H$ is contained in at most $k$ of the guests (the "hitcount" of each vertex is at most $k$ ); every $t$ -global cover is also $t$ -local, so $c_{\mathrm{l}}^{\mathcal{G}}(H) \le c_{\mathrm{g}}^{\mathcal{G}}(H)$ . Local covers carry algorithmic meaning: for covers by complete bipartite guests, the source paper observes that if each vertex of an $n$ -vertex graph lies in at most $t$ of the guests, then few bits suffice to represent each vertex — its at most $t$ guest indices together with the side it occupies in each guest — and adjacency of two vertices can be tested in $O(t\log n)$ time, because two vertices are adjacent exactly when they lie on opposite sides of a common guest.

Two guest classes are central here: $\mathcal{B}$ , the class of all bipartite graphs, and $\mathcal{B}_{\mathrm{c}}$ , the class of all complete bipartite graphs (bicliques). The fractional chromatic number $\chi_{\mathrm{f}}(H)$ is defined via $a:b$ -colorings: each vertex receives a set of $b$ colors out of $[a]$ such that adjacent vertices receive disjoint color sets, and $\chi_{\mathrm{f}}(H)$ is the infimum of $a/b$ over all such colorings; it is always rational and satisfies $\omega(H) \le \chi_{\mathrm{f}}(H) \le \chi(H)$ , where $\chi$ is the ordinary chromatic number. A standard family separating $\chi_{\mathrm{f}}$ from $\chi$ is the Kneser graphs $K_{a:b}$ , whose vertices are the $b$ -element subsets of $[a]$ , with two vertices adjacent when the corresponding sets are disjoint: as recorded in the source paper, $\chi_{\mathrm{f}}(K_{a:b}) = a/b$ while $\chi(K_{a:b}) = a-2b+2$ , so the chromatic number grows without bound along families with bounded ratio $a/b$ .

The global bipartite covering number is exactly understood: Harary, Hsu and Miller proved in 1977 that $c_{\mathrm{g}}^{\mathcal{B}}(H) = \lceil \log_2(\chi(H))\rceil$ for every graph $H$ , so the global number is completely controlled by the chromatic number. The local variant was introduced by Fishburn and Hammer under the name bipartite degree (they used complete bipartite guests) and was placed into the general covering-number framework of Knauer and Ueckerdt (2016). For complete graphs the local value is also classical: $c_{\mathrm{l}}^{\mathcal{B}_{\mathrm{c}}}(K_n) = \lceil \log_2 n\rceil$ , a result from the 1960s theory of Boolean contact circuits that the source paper recovers as a consequence of its lower bound.

Goetze and Schwebler (2026) proved the local analogue of the Harary–Hsu–Miller lower bound: $c_{\mathrm{l}}^{\mathcal{B}}(H) \ge \lceil \log_2(\chi_{\mathrm{f}}(H))\rceil$ for every graph $H$ , which is tight on complete graphs. The local number is, however, not controlled by the ordinary chromatic number: shift graphs (the graph whose vertices are the edges of a digraph $D$ , adjacent when the head of one edge equals the tail of the other) have $c_{\mathrm{l}}^{\mathcal{B}} \le 2$ while their chromatic number is unbounded, as shown by Goetze, Stumpf and Ueckerdt. This leaves a genuine one-sided gap in the fractional regime: no upper bound on $c_{\mathrm{l}}^{\mathcal{B}}(H)$ in terms of $\chi_{\mathrm{f}}(H)$ is known beyond the trivial $c_{\mathrm{l}}^{\mathcal{B}}(H) \le c_{\mathrm{g}}^{\mathcal{B}}(H) = \lceil \log_2(\chi(H))\rceil$ , which is vacuous on families with bounded $\chi_{\mathrm{f}}$ and unbounded $\chi$ , such as Kneser graphs. The source paper poses the boundedness question below as its leading open problem and conjectures a negative answer, expecting the separation to occur already among Kneser graphs $K_{a:b}$ with bounded ratio $a/b$ . Note that any counterexample family must have unbounded ordinary chromatic number, by the trivial bound just quoted.

Problem Statement

This is Question 6.1 of Goetze and Schwebler (arXiv:2607.18833). Let $\mathcal{B}$ denote the class of all bipartite graphs and, for a real number $r \ge 2$ , let $\mathcal{F}_r = \{G : \chi_{\mathrm{f}}(G) \le r\}$ ; note that $\mathcal{F}_2 = \mathcal{B}$ , since the graphs of fractional chromatic number at most 2 are exactly the bipartite graphs.

(i) Does there exist a function $f$ such that $c_{\mathrm{l}}^{\mathcal{B}}(H) \le f(\chi_{\mathrm{f}}(H))$ for every graph $H$ ?

(ii) More generally, does there exist, for every real $r \ge 2$ , a function $f_r$ such that $c_{\mathrm{l}}^{\mathcal{F}_r}(H) \le f_r(\chi_{\mathrm{f}}(H))$ for every graph $H$ ?

The question is resolved either by exhibiting the bounding function(s) together with a proof that every graph admits a locally sparse cover of the required kind, or by exhibiting an infinite family of graphs whose fractional chromatic numbers are bounded by a constant while their local $\mathcal{B}$ -covering numbers (and, for part (ii), local $\mathcal{F}_r$ -covering numbers for some $r$ ) grow without bound. Part (i) is the case $r=2$ of part (ii), so a positive answer to (ii) implies one to (i), and a negative answer to (i) is the strongest form of refutation. The source authors conjecture the answer is negative; any refuting family must have unbounded ordinary chromatic number.

References

Miriam Goetze and Lucas Schwebler. On the Computational Complexity of Local and Global Covering Numbers. arXiv:2607.18833, 2026. doi:10.48550/arXiv.2607.18833, https://arxiv.org/abs/2607.18833
Miriam Goetze, Peter Stumpf, and Torsten Ueckerdt. Boundedness and Separation in the Graph Covering Number Framework. arXiv:2504.17458, 2025. doi:10.48550/arXiv.2504.17458, https://arxiv.org/abs/2504.17458
Anna Gujgiczer, Márton Marits, and Kenta Ozeki. Cover numbers by graph families bounded by certain graph parameters. arXiv:2607.12353, 2026. doi:10.48550/arXiv.2607.12353, https://arxiv.org/abs/2607.12353
Frank Harary, Derbiau Hsu, and Zevi Miller. The biparticity of a graph. Journal of Graph Theory, 1(2):131–133, 1977. doi:10.1002/jgt.3190010208, https://doi.org/10.1002/jgt.3190010208
Peter C. Fishburn and Peter L. Hammer. Bipartite dimensions and bipartite degrees of graphs. Discrete Mathematics, 160(1–3):127–148, 1996. doi:10.1016/0012-365X(95)00154-O, https://doi.org/10.1016/0012-365X(95)00154-O
Kolja Knauer and Torsten Ueckerdt. Three ways to cover a graph. Discrete Mathematics, 339(2):745–758, 2016. doi:10.1016/j.disc.2015.10.023, https://doi.org/10.1016/j.disc.2015.10.023