Cover numbers by certain graph families

M\'arton Marits

REVIEW 3 major objections 5 minor 1 cited by

Cover numbers by certain graph families

T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For any non-decreasing $f$ with $f(x)\ge x$, the minimum number of graphs with $\chi\le f(\omega)$ needed to cover the edges of $G$ is exactly $\lceil \log\chi(G)/\log f(\omega(G))\rceil$.

desk verdict Theorem 3 is a clean, sound extension of Harary–Hsu–Miller, but Theorem 7 has a concrete arithmetic error that leaves the first separation in the chain unproved. read the letter →

arxiv 2412.08980 v2 pith:CUIJLZMQ submitted 2024-12-12 math.CO

Márton Marits This is my paper · ORCID

classification math.CO MSC 05C1505C1705C70

keywords graphcoveringcovernumberchromaticcliquechi-boundedfamiliesperfectgraphsunipolarbipartite

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies how many graphs from a prescribed family are needed to cover all edges of a given graph. Its main result is an exact formula for the cover number by any class of the form $\{G : \chi(G) \le f(\omega(G))\}$, where $f$ is non-decreasing and $f(x) \ge x$: the answer is $\left\lceil \log \chi(G) / \log f(\omega(G)) \right\rceil$. This extends the classical biparticity formula, in which $f$ is constant. The paper then shows that the cover numbers by the classes of graphs with $\chi=\omega$, perfect graphs, generalized split graphs, co-unipolar graphs, and bipartite graphs form a chain, and that every gap in this chain can be made arbitrarily large. It also proves that the cover number by unipolar graphs is unbounded even when both $\chi$ and $\omega$ are fixed, so no formula in those two parameters alone can describe it.

What carries the argument

The central mechanism is a pair of complementary arguments around a product coloring. For the lower bound, given a cover by $t$ graphs each with $\chi \le f(\omega)$, the product of optimal colorings gives a coloring of $G$ with at most $f(\omega(G))^t$ colors, forcing $t \ge \log_{f(\omega(G))}\chi(G)$. For the upper bound, an optimal $\chi(G)$-coloring is reinterpreted as a map from each vertex to a function $\phi_x : A \to \{1,\dots,f(\omega(G))\}$ with $|A|=\lceil \log_{f(\omega(G))}\chi(G)\rceil$; each coordinate $i\in A$ defines a covering graph $G_i$ containing exactly the edges whose endpoints differ in coordinate $i$. A maximal clique of $G$ is colored by distinct constant functions, so every $G_i$ still contains that clique and hence has $\omega(G_i)=\omega(G)$, while each $G_i$ is colored by $f(\omega(G))$ colors via the coordinate value. This two-sided construction is what makes the formula exact rather than an inequality.

What would settle it

Exhaustively compute $c_{\{\chi\le f(\omega)\}}$ for all graphs with up to seven vertices for $f(x)=x$ and $f(x)=2x$; if the result ever differs from $\lceil \log\chi(G)/\log f(\omega(G))\rceil$, the main formula is false. A second check, specific to the chain gaps, is to compute the comparability cover number of the perfect graphs from [3]; a value below the claimed bound would break Theorem 8.

Watch

Extended reading notes

Core claim

At the paper's center is the exact formula $c_{\{\chi \le f(\omega)\}}(G) = \left\lceil \frac{\log \chi(G)}{\log f(\omega(G))} \right\rceil$, valid for every non-decreasing function $f$ with $f(x)\ge x$. The lower bound comes from a product coloring: if $G$ is the edge-union of $t$ graphs each with chromatic number at most $f(\omega(G))$, then the coordinatewise product of their optimal colorings colors $G$ with at most $f(\omega(G))^t$ colors. The upper bound encodes an optimal $\chi(G)$-coloring as a family of functions from a coordinate set of size $\lceil \log_{f(\omega(G))} \chi(G)\rceil$ into $\{1,\dots,f(\omega(G))\}$; each coordinate then gives one covering graph, and a maximal clique is colored by constant functions (possible because $f(\omega(G))\ge \omega(G)$), so every covering graph has clique number $\omega(G)$. With $f$ equal to the identity, the formula reads $c_{\{\chi=\omega\}}(G)=\lceil \log \chi(G)/\log \omega(G)\rceil$. The paper further proves a five-term chain $c_{\{\chi=\omega\}}\le c_{\mathrm{PERF}}\le c_{\mathrm{GSP}}\le c_{\mathrm{coUNIP}}\le c_{\mathrm{BIP}}$ with arbitrarily large gaps at every step, and shows that $c_{\mathrm{UNIP}}$ is unbounded on bipartite hypercubes, so no function of $\chi$ and $\omega$ alone can express it.

Load-bearing premise

The proof that $c_{\mathrm{PERF}}$ and $c_{\mathrm{GSP}}$ can be made arbitrarily far apart rests on two statements taken from the companion preprint [3] — that some perfect graphs have arbitrarily large comparability cover number and that every generalized split graph has comparability cover number at most two — and neither statement is proved in this paper.

Editorial extensions

If this is right

For any $\chi$-bounded class $\mathcal P$ with binding function $f$, Corollary 5 supplies the universal lower bound $c_{\mathcal P}(G)\ge \lceil \log \chi(G)/\log f(\omega(G))\rceil$ for every graph $G$.
Taking $f$ constant recovers the classical biparticity formula, so the main theorem is a direct generalization rather than an isolated result.
The arbitrarily large gap between $c_{\{\chi=\omega\}}$ and $c_{\mathrm{PERF}}$ shows that covering a graph by perfect graphs can be much harder than covering it by graphs that merely satisfy $\chi=\omega$.
The hypercube construction shows $c_{\mathrm{UNIP}}$ can grow as $d$ on graphs with $\chi=\omega=2$, so any future formula for $c_{\mathrm{UNIP}}$ must depend on parameters beyond chromatic and clique numbers.
The four gap theorems give explicit witness graphs for each separation, so the chain's strictness is witnessed by concrete finite graphs rather than a limit argument alone.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The lower-bound certificate in Corollary 5 could be repurposed as a detection tool: to prove that a class is not $\chi$-bounded, it suffices to exhibit graphs whose cover number by that class falls below the predicted bound.
The coordinate-splitting construction in the upper bound looks adaptable to other vertex parameters, such as degeneracy or maximum degree, and might yield analogous exact cover numbers for classes defined by those parameters.
The chain gaps suggest the edge-cover number is a finer discriminator of graph classes than chromatic number; one could test whether thickness (covering by planar graphs) exhibits similar gaps when restricted to perfect graphs or other subclasses.
The two external inputs used in Theorem 8—unbounded comparability cover number on perfect graphs and the two-comparability-graph bound for generalized split graphs—come from the companion preprint [3]; replacing them with self-contained proofs would make the perfect-versus-GSP separation independent of outside results.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The main result is the exact formula in Theorem 3. It is sound and it is a real extension of Harary–Hsu–Miller: for any nondecreasing f with f(x) ≥ x, the cover number by {χ ≤ f(ω)} is ceil(log χ / log f(ω)). The proof is straightforward but correct: product coloring for the lower bound, and for the upper bound a maximal clique colored by constant functions so that each G_i keeps ω(G_i) = ω(G). Corollary 5 putting chi-boundedness into cover-number terms is a neat touch. This part deserves to be in the literature.

The trouble is Theorem 7, which the abstract relies on to claim all inequalities in the chain can be arbitrarily separated. The proof constructs Z_{2ℓ} ∪ K_{2ℓ} and says covering Z_{2ℓ} by perfect graphs needs at least log(2ℓ) = ℓ graphs. That equality is wrong; Corollary 4 gives ceil(log(2ℓ)). For ℓ = 4, Z_8 ∪ K_8 has c_PERF = 3, not 4. The construction cannot force the advertised separation between c_{χ=ω} and c_PERF. The "If k = 2, then we are done" line is also garbled—the graph as built has c_{χ=ω} = 1, not 2, unless an R_k is added. So the first separation theorem is not proved as written, and the abstract's "at each inequality" overclaims.

Other soft spots: Theorem 8 leans on two results from [3], an overlapping-author preprint, so it needs independent verification. Theorem 9's "mixed strategy" argument is compressed, but the claim looks plausible and is not central.

Bottom line: the formula is solid and significant. The separation chain needs repair, but the central theorem and Theorems 9–11 stand on their own. A serious referee should see this; I'd send it out with a note to verify Theorem 7 and the dependency in Theorem 8.

Referee Report

3 major / 5 minor

Summary. The paper studies edge-cover numbers by graph families: the minimum number of graphs from a class P needed to cover the edge set of a graph G. Its main result, Theorem 3, gives an exact formula for the cover number by the class {G : χ(G) ≤ f(ω(G))} for any non-decreasing function f with f(x) ≥ x, namely c(G) = ⌈log χ(G)/log f(ω(G))⌉. The proof is a clean two-sided argument: a product coloring over an optimal cover gives the lower bound, and an encoding of colors as functions gives the upper bound while controlling the clique number. The paper then defines a chain of cover numbers for the classes {χ=ω}, perfect graphs, generalized split graphs, co-unipolar graphs, and bipartite graphs, and claims four separation theorems showing that each inequality can be arbitrarily wide, plus a non-expressibility result for unipolar graphs. The secondary results are less solid than the main theorem and contain several errors that need repair.

Significance. If Theorem 3 stands, it is an elegant and useful generalization of the classical Harary–Hsu–Miller formula for biparticity, and it supplies a certificate-style lower bound for any χ-bounded class via Corollary 5. The main proof is elementary, self-contained, and correct. The chain of inequalities and the proposed separations are interesting and would give a fairly complete picture of the behavior of these cover numbers. However, the separation theorems are not yet established as written: Theorem 7 has a substantive gap, Theorem 8 depends entirely on an overlapping-author preprint, and Theorems 9 and 10 have incorrect statements involving non-integer logarithms. These issues do not affect Theorem 3, but they do affect the paper's advertised secondary claims.

major comments (3)

[2, proof of Theorem 7] The proof of Theorem 7 is incorrect as written. For G = Z_{2ℓ} ∪ K_{2ℓ}, Corollary 4 yields c_{χ=ω}(G) = ⌈log(2ℓ)/log(2ℓ)⌉ = 1, so this graph has c_{χ=ω} = k only when k = 1; the sentence 'If k=2, then we are done' appears to be a typo for k=1. Moreover, the lower bound c_PERF(G) ≥ ℓ is obtained from the identity log(2ℓ) = ℓ, but the correct bound for a triangle-free graph Z_{2ℓ} with chromatic number 2ℓ is c_PERF(Z_{2ℓ}) = ⌈log(2ℓ)⌉, because every perfect subgraph of Z_{2ℓ} is bipartite. For ℓ = 4 the construction gives c_PERF(G) = 3, not ≥ 4. A repair would require a triangle-free graph with chromatic number 2^ℓ and an additional component R_k with χ(R_k) = ω(R_k)^k and ω(R_k) ≥ 2^ℓ; the proof as written does not do this. Since Theorem 7 is the first of the claimed unbounded separations in the chain, this is a load-bearing gap.
[2, proof of Theorem 8] Theorem 8 is not proved within the manuscript: the proof uses two results from the preprint [3] — the existence of perfect graphs with arbitrarily large comparability cover number, and the assertion that every generalized split graph has comparability cover number at most 2 — without including proofs or even complete statements of these results. Because [3] is an overlapping-author preprint, the claimed separation between c_PERF and c_GSP is conditional on external work. The authors should either prove the needed lemmas in this paper or cite a published, verifiable version before this theorem can be accepted as part of the paper's contribution.
[Theorems 9 and 10] The statements of Theorems 9 and 10 are not well-formed when the logarithms are not integers. In Theorem 9, for k = 2 and ℓ = 3 the claimed value is min{2, log_2 3} = 1.58, but a cover number must be an integer; the construction actually supports min{k, ⌈log_2 ℓ⌉} (the value 2 in this example). In Theorem 10, c_BIP(K_k) = ⌈log_2 k⌉, so the asserted equality c_BIP(B_k) = log_2 k holds only when k is a power of 2; for k = 3 the value is 2, not log_2 3. The statements should be repaired with ceilings or restricted to powers of two, and the 'mixed strategy' sentence in the proof of Theorem 9 should be replaced by a precise lower-bound argument.

minor comments (5)

[Abstract and Theorem 3] The abstract says the formula holds for an 'arbitrary non-decreasing function f', but Theorem 3 requires the additional hypothesis f(x) ≥ x; the abstract should state this condition.
[Theorem 3 statement] The left-hand side of Theorem 3 writes c_{χ≤f(ω)} without the argument (G); the notation in Theorems 2 and 3 should be aligned for clarity.
[Proof of Theorem 7] There is a typo in the definition of Z_{2ℓ}: 'χ(Z_ℓ) = 2ℓ' should read 'χ(Z_{2ℓ}) = 2ℓ'.
[Proof of Theorem 11] The final sentence of the lower-bound argument says 'its upper integer part will be d'; this should be phrased as 'the ceiling is d'.
[Theorem 8] The dependence on the preprint [3] should be flagged in the introduction or in the statement of Theorem 8, so that the reader knows the proof is not self-contained.

Circularity Check

1 steps flagged · score 4.0 of 10

Main formula is derived independently; the only circularity-burden step is Theorem 8's dependence on an unproved same-author preprint.

self citation load bearing [Proof of Theorem 8 (Section 2), relying on [3, Theorems 4 and 8]]
"We use the construction from [3, Theorem 8]. In that paper, it is pro ven that there exist perfect graphs with arbitrarily large cover number by c omparability graphs. In the same paper, it is also proved [3, Theorem 4] that all GSP graphs have cCOMP ≤ 2."

Theorem 8 is the paper's evidence that c_PERF and c_GSP can differ arbitrarily in the advertised inequality chain. Its lower bound c_GSP(H_k) ≥ k/2 is obtained by chaining two results imported from [3]: a perfect graph with c_COMP = k, and the bound c_COMP(G) ≤ 2 for every GSP graph. Reference [3] is a preprint sharing author M. Marits with the present paper, and neither imported result is proved or independently verified in this manuscript. The derivation therefore rests on a load-bearing same-author citation rather than on a self-contained argument; if the cited theorems were absent, Theorem 8 would have no demonstrated content. This does not infect Theorem 3, which is proved directly.

full rationale

The core result, Theorem 3, is proved from first principles using only the definition of χ(G), ω(G), and the cover number; the lower bound uses an optimal cover and product coloring, the upper bound constructs a cover from an optimal vertex coloring, with f majorizing the identity ensuring the maximal clique can be constant-colored. This is independent of the paper's other claims and reproduces Harary-Hsu-Miller as a constant-function special case. The inequality chain and corollaries follow from P ⊆ Q ⇒ cP ≥ cQ, which is proved in Theorem 1. The one load-bearing self-citation is Theorem 8, which imports two unproved-in-this-paper results from [3] by overlapping authorship; this justifies the claimed unbounded gap between c_PERF and c_GSP. That is a genuine circularity burden but it is confined to a supporting separation claim; the central formula and the biparticity-based chain are not reduced to their own inputs. Separately, the proof of Theorem 7 contains a non-circular arithmetic gap (it writes log_2(2ℓ) = ℓ), which affects the advertised first separation as written; this is a correctness issue rather than a circularity one.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The proof relies on standard constructions (Zykov graphs), classical theorems (Mirsky, Harary-Hsu-Miller), and two results from an overlapping-author preprint [3]. No numerical parameters or ad hoc entities are introduced.

assumptions (4)

standard math Zykov's construction produces graphs with prescribed clique number and chromatic number, used for Z_{2ℓ} and R_k.
Invoked in the proof of Theorem 7; standard result in extremal graph theory.
standard math Mirsky's theorem implies every comparability graph is perfect.
Invoked in the proof of Theorem 8; classical result.
standard math Harary, Hsu and Miller's formula: c_BIP(G) = ceil(log χ(G)).
Used as the baseline in Theorems 9 and 10 and in the chain of inequalities.
domain assumption From [3]: perfect graphs with arbitrarily large comparability cover number exist; every generalized split graph has comparability cover number at most 2.
Both results are used in the proof of Theorem 8 and are not proved in this paper; [3] shares an author with this paper, so independent checking is advisable.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Cover numbers by certain graph families." pith.science (2026). https://pith.science/paper/CUIJLZMQ

@misc{pith2026241208980,
  author       = {Pith},
  title        = {Pith review of: Cover numbers by certain graph families},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CUIJLZMQ}},
  note         = {Machine review of arXiv:2412.08980}
}

abstract

We define the cover number of a graph $G$ by a graph class $\mathcal P$ as the minimum number of graphs of class $\mathcal P$ required to cover the edge set of $G$. Taking inspiration from a paper by Harary, Hsu and Miller, we find an exact formula for the cover number by the graph classes $\{ G \mid \chi(G) \leq f(\omega(G))\}$ for an arbitrary non-decreasing function $f$. After this, we establish a chain of inequalities with five cover numbers, the one by the class $\{ G \mid \chi(G) = \omega(G)\}$, by the class of perfect graphs, generalized split graphs, co-unipolar graphs and finally by bipartite graphs. We prove that at each inequality, the difference between the two sides can grow arbitrarily large. We also prove that the cover number by unipolar graphs cannot be expressed in terms of the chromatic or the clique number.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Boolean combinations of graphs
math.CO 2024-12 conditional novelty 7.0 of 10

Boolean combinations of graphs give new characterizations of subexponential, subfactorial and structurally bounded degree graph classes, and yield new polynomial and linear chi-boundedness results.

Reference graph

Works this paper leans on

10 extracted references · 9 canonical work pages · cited by 1 Pith paper

[3]

Gy´ arf´ as, A., Marits, M., & T´ oth, G. (2024). Partitioning perfect graphs into comparability graphs. arXiv preprint arXiv:2408.13523

arXiv 2024
[1]

Chudnovsky, M., Robertson, N., Seymour, P., & Thomas, R. (200 6). The strong perfect graph theorem. Annals of mathematics , 51-229

work page
[2]

Gy´ arf´ as, A. (1987). Problems from the world surrounding pe rfect graphs. Applicationes Mathematicae, 19(3-4), 413-441

work page 1987
[4]

Harary, F. (1970). Covering and packing in graphs, I. Annals of the New York Academy of Sciences , 175(1), 198-205

work page 1970
[5]

Harary, F., Hsu, D., & Miller, Z. (1977). The biparticity of a graph. Journal of graph theory , 1(2), 131-133

work page 1977
[6]

Mirsky, L. (1971). A dual of Dilworth’s decomposition theorem. The Amer- ican Mathematical Monthly , 78(8), 876-877

work page 1971
[7]

Mutzel, P., Odenthal, T., & Scharbrodt, M. (1998). The thicknes s of graphs: a survey. Graphs and combinatorics , 14, 59-73

work page 1998
[8]

J., & Steger, A

Pr¨ omel, H. J., & Steger, A. (1992). Almost all Berge graphs are perfect. Combinatorics, Probability and Computing , 1(1), 53-79

work page 1992

Show all 10 references

[9]

Scott, A., & Seymour, P. (2020). A survey of χ-boundedness. Journal of Graph Theory, 95(3), 473-504. 7

2020
[10]

Zykov, A. A. (1949). On some properties of linear complexes. Matematich- eskii sbornik , 66(2), 163-188. 8

1949

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [3]

Gy´ arf´ as, A., Marits, M., & T´ oth, G. (2024). Partitioning perfect graphs into comparability graphs. arXiv preprint arXiv:2408.13523

arXiv 2024

[2] [1]

Chudnovsky, M., Robertson, N., Seymour, P., & Thomas, R. (200 6). The strong perfect graph theorem. Annals of mathematics , 51-229

work page

[3] [2]

Gy´ arf´ as, A. (1987). Problems from the world surrounding pe rfect graphs. Applicationes Mathematicae, 19(3-4), 413-441

work page 1987

[4] [4]

Harary, F. (1970). Covering and packing in graphs, I. Annals of the New York Academy of Sciences , 175(1), 198-205

work page 1970

[5] [5]

Harary, F., Hsu, D., & Miller, Z. (1977). The biparticity of a graph. Journal of graph theory , 1(2), 131-133

work page 1977

[6] [6]

Mirsky, L. (1971). A dual of Dilworth’s decomposition theorem. The Amer- ican Mathematical Monthly , 78(8), 876-877

work page 1971

[7] [7]

Mutzel, P., Odenthal, T., & Scharbrodt, M. (1998). The thicknes s of graphs: a survey. Graphs and combinatorics , 14, 59-73

work page 1998

[8] [8]

J., & Steger, A

Pr¨ omel, H. J., & Steger, A. (1992). Almost all Berge graphs are perfect. Combinatorics, Probability and Computing , 1(1), 53-79

work page 1992