{"id":"42be7f87-4f69-4701-b43e-740f66cd378a","arxiv_id":"2412.08980","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For any non-decreasing function f with f(x)≥x, the minimum number of graphs satisfying χ≤f(ω) needed to cover a graph G equals ceil(log χ(G)/log f(ω(G))).","lead":"This paper studies edge-covering of graphs: how many pieces from a restricted graph family are needed to cover every edge of a large graph. It finds an exact formula for one broad family and shows that several natural covering measures can differ by arbitrarily large amounts.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 7's proof asserts log_2(2ℓ)=ℓ and uses χ=2ℓ; for ℓ=4 the constructed G=Z_8∪K_8 has c_PERF=3, not ≥4, so the first separation is unproved as written.","rationale":"The main formula, Theorem 3, appears correct: the lower bound via product coloring and the upper bound via the color-as-function construction both check out. The load-bearing weakness is in the advertised chain of separations. Theorem 7, the first separation, has an internally demonstrable numerical error: for ℓ=4 the stated construction gives c_PERF=3 rather than ≥4. This is not merely an external citation issue; it can be checked from the paper itself. The construction is almost certainly repairable by replacing Z_{2ℓ} with Z_{2^ℓ}, so this warrants conditional acceptance rather than rejection. I agree with the reader that Theorem 8's dependence on [3] is a second concern, but the Theorem 7 arithmetic is the more urgent, self-contained flaw.","tokens_in":5478,"tokens_out":37269,"duration_ms":348793,"concrete_test":"Run the ℓ=4 check: take a triangle-free Z with χ=8, set G=Z∪K_8, and exhibit the 3-graph perfect cover described above. If it exists, the printed Theorem 7 proof is refuted. Then test the corrected construction with χ(Z)=2^ℓ: verify that c_BIP(Z)=ℓ and that the same restriction argument yields c_PERF(G)≥ℓ, which would show the theorem is repairable but the manuscript parameters must change.","verdict_should_be":"UNCHANGED","load_bearing_attack":"For ℓ=4, the graph constructed in the proof of Theorem 7 is G=Z_8∪K_8, where Z_8 is triangle-free with χ=8. Any perfect graph restricted to Z_8 is bipartite, so any perfect cover of G induces a bipartite cover of Z_8; hence c_PERF(G)≥c_BIP(Z_8)=3. Conversely, cover Z_8 by three bipartite graphs and put all edges of K_8 into one of them; each cover graph is perfect (a disjoint union of a clique and bipartite graphs), so c_PERF(G)≤3. Thus c_PERF(G)=3, while the proof claims the lower bound log_2(2ℓ)=ℓ=4. The error is the assertion log_2(2ℓ)=ℓ: with χ=2ℓ, Corollary 4 gives only ⌈log_2(2ℓ)⌉, and the construction would need χ=2^ℓ to reach the intended bound. The advertised separation between c_{χ=ω} and c_PERF is therefore not proved as written. This does not affect Theorem 3, whose proof is sound.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":5765,"tokens_out":24937,"duration_ms":270886,"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":[{"comment":"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.","section":"2, proof of Theorem 7"},{"comment":"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.","section":"2, proof of Theorem 8"},{"comment":"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.","section":"Theorems 9 and 10"}],"minor_comments":[{"comment":"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.","section":"Abstract and Theorem 3"},{"comment":"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.","section":"Theorem 3 statement"},{"comment":"There is a typo in the definition of Z_{2ℓ}: 'χ(Z_ℓ) = 2ℓ' should read 'χ(Z_{2ℓ}) = 2ℓ'.","section":"Proof of Theorem 7"},{"comment":"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'.","section":"Proof of Theorem 11"},{"comment":"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.","section":"Theorem 8"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is solid and worth publishing, but the secondary separation theorems are not yet at the standard claimed in the abstract. The arithmetic error in Theorem 7 is substantive, though repairable with a different construction; Theorems 9 and 10 need straightforward but necessary corrections with ceilings or power-of-two restrictions; and Theorem 8's reliance on the overlapping-author preprint [3] should be resolved before publication. I would be inclined to accept after these points are addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nOther 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.\n\nBottom 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.","headline":"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.","tokens_in":6262,"tokens_out":4161,"would_cite":true,"duration_ms":40121,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C17","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"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$.","keywords":["graph covering","cover number","chromatic number","clique number","chi-bounded graph families","perfect graphs","unipolar graphs","bipartite graphs"],"falsifier":"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.","tokens_in":5307,"feed_emoji":"🧩","tokens_out":17532,"duration_ms":144172,"temperature":0.7,"pith_summary":"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.","feed_headline":"One formula gives the edge-cover number for every χ-bounded class","feed_subtitle":"Extends the classic bipartite cover formula; the gaps among five cover numbers grow without bound.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Establishes the biparticity formula $c_{\\mathrm{BIP}}(G)=\\lceil\\log\\chi(G)\\rceil$ for constant $f$, the base case that Theorem 3 extends.","marker":"[5]"},{"why":"Provides the two external results needed in Theorem 8: perfect graphs with arbitrarily large comparability cover number, and generalized split graphs with comparability cover number at most two.","marker":"[3]"},{"why":"Supplies graphs $Z_{2\\ell}$ with clique number two and chromatic number $2\\ell$, used to build the gap examples in Theorem 7.","marker":"[10]"},{"why":"Yields the fact that comparability graphs are perfect, which lets the proof lower-bound $c_{\\mathrm{PERF}}$ via comparability cover numbers.","marker":"[6]"},{"why":"Introduces $\\chi$-bounded classes and their binding functions, giving the family $\\{\\chi\\le f(\\omega)\\}$ that the main formula studies.","marker":"[2]"}],"fun_headline_variants":["Exact cover number for every χ-bounded class","Five cover numbers, gaps that grow without bound","Unipolar cover number: no χ,ω formula exists","Cover numbers: exact formula for χ-bounded, unbounded gaps"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Exact cover number for every χ-bounded class","Five cover numbers, gaps that grow without bound","Unipolar cover number: no χ,ω formula exists","Cover numbers: exact formula for χ-bounded, unbounded gaps"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000752,"raw_usage":{"total_tokens":3402,"prompt_tokens":1059,"completion_tokens":2343,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":675,"completion_tokens_details":{"reasoning_tokens":2277}},"tokens_in":675,"tokens_out":2343,"duration_ms":16896,"temperature":1.0,"reasoning_tokens":2277,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T17:22:22.941320+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the biparticity formula $c_{\\mathrm{BIP}}(G)=\\lceil\\log\\chi(G)\\rceil$ for constant $f$, the base case that Theorem 3 extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies graphs $Z_{2\\ell}$ with clique number two and chromatic number $2\\ell$, used to build the gap examples in Theorem 7."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Yields the fact that comparability graphs are perfect, which lets the proof lower-bound $c_{\\mathrm{PERF}}$ via comparability cover numbers."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces $\\chi$-bounded classes and their binding functions, giving the family $\\{\\chi\\le f(\\omega)\\}$ that the main formula studies."}],"review_version":1}