{"id":"539dcf5b-41f6-4748-a8ad-b4ebc4899f2e","arxiv_id":"2411.16547","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For graphs G and H, hom-complexity C(G;H) is the fewest H-colourable subgraphs covering G, and when H has equal clique and chromatic number it equals ceil(log_{χ(H)} χ(G)), recovering known formulas for ℓ-particity and bipartite dimension.","lead":"The authors define hom-complexity, the fewest subgraphs into which a graph G must be split so that each subgraph maps homomorphically into a target graph H, plus an injective version. They prove bounds and show the invariant recovers classical formulas such as the ℓ-particity and the bipartite dimension of complete graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof of Theorem 3.36 has repairable gaps (omitted multiples of ℓ, duplicate G_{k+1}=G_k), but Corollary 3.34 is unaffected.","rationale":"The reader's weakest assumption correctly identifies the proof gap in Theorem 3.36. I agree that the induction omits multiples of ℓ and that the duplicate subgraph at j=ℓ^k conflicts with Definition 3.1's distinctness requirement. However, this gap is not load-bearing for the paper's main formula: Corollary 3.34 is proved from Theorem 3.26 (lower bound) and Theorem 3.30 (upper bound), and neither depends on Theorem 3.36. Proposition 3.28, which supplies the upper bound, is sound once one reads its decomposition correctly: the second piece is a complete i-partite graph, hence K_i-colourable, and the first piece is a disjoint union of cliques whose hom-complexity is max C(K_ℓ;K_i). The Theorem 3.36 gaps affect only Theorem 4.9(1), and even there the equality β_ℓ(G)=C(G;K_ℓ) is repairable and independently known (via the known formula β_ℓ(G)=⌈log_ℓ χ(G)⌉). Thus the verdict should remain CONDITIONAL: the identified flaw is real but repairable, and the central chromatic-number formula is not threatened.","tokens_in":26084,"tokens_out":24798,"duration_ms":236309,"concrete_test":"Run Theorem 3.36's recursive construction for ℓ=3, k=2 and enumerate j=3,...,9. The proof as written covers j=3,4,5,7,8,9 but not j=6; check whether j=6 is decomposed as (K_2⊔K_2⊔K_2) ∪ K_{2,2,2} into two distinct 3-partite spanning subgraphs of K_6. If that repair works, also test the endpoint j=27 for ℓ=3, k=3: replace the duplicate G_{k+1}=G_k by the complete 3-partite graph K_{9,9,9} and verify that all three subgraphs are distinct and 3-partite.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The weakest link is the proof of Theorem 3.36(1), which is used only for the equality with ℓ-particity in Theorem 4.9(1), not for the central formula C(G;H)=⌈log_{χ(H)}χ(G)⌉. In the base k=2 step, the displayed cases cover j=ℓ, j=ℓ², and j=(m−1)ℓ+r with 1≤r<ℓ, but omit j=mℓ for 2≤m<ℓ, e.g. ℓ=3, j=6. In the induction step, the lower endpoint j=ℓ^k is handled by setting G_{k+1}=G_k, which violates the distinctness requirement in Definition 3.1. Both gaps are repairable: an omitted multiple j=mℓ admits the decomposition (⊔_{t=1}^ℓ K_m) ∪ K_{m,...,m}, with both pieces ℓ-partite, and the duplicate G_{k+1} can be replaced by a different complete ℓ-partite spanning subgraph, e.g. K_{ℓ^{k-1},...,ℓ^{k-1}}. Because the lower bound (Theorem 3.26) and upper bound (Theorem 3.30, via Proposition 3.28) are sound, Corollary 3.34 and the formula C(G;K_ℓ)=⌈log_ℓ χ(G)⌉ stand independently. The gap only weakens the paper's own proof of β_ℓ(G)=C(G;K_ℓ), an equality already known in the literature.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines hom-complexity C(G;H) as the least k such that G is the union of k H-colourable subgraphs, and injective hom-complexity IC(G;H) analogously with injective homomorphisms into H. It establishes basic properties (monotonicity under graph homomorphisms, subadditivity, product inequalities), a lower bound χ(G) ≤ χ(H)^{C(G;H)}, and an upper bound C(G;H) ≤ min{k : χ(G) ≤ ω(H)^k}. These yield Corollary 3.34: for simple graphs G,H with χ(G) ≥ 2 and ω(H) = χ(H) ≥ 2, C(G;H) = ⌈log_{χ(H)} χ(G)⌉. The paper then connects C to clique covering, ℓ-particity, and bipartite dimension, proving C(G;K_ℓ) = β_ℓ(G) and C(K_n;K_2) = d(K_n), and recovering known formulas β_ℓ(G) = ⌈log_ℓ χ(G)⌉ and d(K_n) = ⌈log_2 n⌉. A data-migration example and suggestions for future work close the paper.","tokens_in":92,"tokens_out":19200,"duration_ms":242385,"significance":"If the proofs are completed, the main formula is a clear, parameter-free characterization: for targets whose clique and chromatic numbers coincide, hom-complexity is determined solely by the two chromatic numbers. This gives a unified derivation of several known covering-number formulas, and the lower/upper bound framework is elementary and transparent. The central formula is obtained without circularity: Corollary 3.34 follows directly from Theorem 3.26 and Theorem 3.30. The equality with ℓ-particity is a genuine connection to the existing literature, but its proof as written depends on Theorem 3.36, where I found repairable gaps. These gaps do not affect Corollary 3.34, but they do affect the proof of one of the paper's advertised main theorems.","major_comments":[{"comment":"In the base case k = 2, the displayed decomposition of K_j for ℓ < j ≤ ℓ^2 covers only j = ℓ, j = ℓ^2, and j = (m−1)ℓ + r with 1 ≤ r < ℓ. This omits the cases j = mℓ with 2 ≤ m < ℓ, for example ℓ = 3 and j = 6. Since Theorem 3.36(2) applies Item (1) to j = χ(G), the proof of Theorem 3.36(2), and hence of Theorem 4.9(1) as written, is incomplete. A repair is available: for j = mℓ, write K_{mℓ} = A ∪ B with A = ⊔_{t=1}^ℓ K_m and B = K_{m,...,m}; A is ℓ-partite after assigning the m vertices of each copy to m distinct color classes while ensuring all ℓ color classes occur across the ℓ copies, and B is the complete ℓ-partite graph on the ℓ copies.","section":"Theorem 3.36(1)"},{"comment":"The proof sets G_{k+1} = G_k, which is a duplicate subgraph. The abstract explicitly requires 'k different subgraphs', while Definition 3.1 does not state distinctness; the paper must resolve this inconsistency. If distinctness is required, the construction violates the definition; if duplicates are allowed, the abstract and related prose should say so. The step is repairable in either reading: replace G_{k+1} by a different spanning ℓ-partite subgraph of K_{ℓ^k}, for instance the complete ℓ-partite graph K_{ℓ^{k-1},...,ℓ^{k-1}} with a partition chosen to avoid coincidence with the previously used subgraphs.","section":"Theorem 3.36(1), induction step at j = ℓ^k"}],"minor_comments":[{"comment":"The abstract contains the malformed string '\\aspas{complexity}', and Section 2 contains the typo 'homomorphsims' in the definition of homomorphisms.","section":"Abstract and Section 2"},{"comment":"In the displayed decomposition of K_j, the parameter ℓ is used before it is defined; the proof should state explicitly that ℓ = ceil(j/i) (or the integer determined by the Euclidean division of j by i).","section":"Proposition 3.28"},{"comment":"The notation 'm = |V(G)| / 2' is typeset in a way that reads as 'm = |V(G)| 2'; please clarify the division and the statement IC(G;K_2) = ⌈|V(G)|/2⌉ for edgeless G.","section":"Remark 3.16"},{"comment":"The abstract's 'k different subgraphs' is not matched by Definition 3.1, which only says 'there exist subgraphs G_1, ..., G_k'. This ambiguity is relevant to the duplicate-subgraph issue in Theorem 3.36 and should be fixed.","section":"Definition 3.1 and abstract"},{"comment":"In the isomorphism-free proof that C(C_{2k};K_2) = 1, the color map uses 'm' for one of the two colors even though m already denotes the cycle length; using the labels 1 and 2 would avoid confusion.","section":"Example 3.19"}],"recommendation":"major_revision","confidential_remarks":"The two gaps in Theorem 3.36 are local and repairable; I found no problem with the central formula Corollary 3.34 or with the lower/upper bound arguments. The contribution is modest but fits a combinatorics journal. I recommend major revision because one of the advertised theorems, Theorem 4.9(1), currently relies on an incomplete proof, even though the underlying statement is believable and the gaps can likely be fixed without changing the paper's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe main formula is solid: for simple graphs G,H with χ(G)≥2 and ω(H)=χ(H), the bound C(G;H)=⌈log_{χ(H)}χ(G)⌉ follows cleanly from the lower bound (Theorem 3.26) and upper bound (Theorem 3.30). Those two theorems are straightforward and correct, and they are the load-bearing parts of the paper. So the headline result is fine.\n\nWhat is genuinely new is the systematic study of hom-complexity as an invariant: the injective version, subadditivity, triangle inequality, product bounds, and the explicit connection to covering numbers. The paper is honest that C(G;H) is formally an H-covering number (Proposition 4.2), so novelty is in the framing and the general formula, not in the raw definition. Recovering β_ℓ(G)=⌈log_ℓ χ(G)⌉ and d(K_n)=⌈log_2 n⌉ as corollaries is a reasonable sanity check, not a flaw.\n\nThe soft spot is the proof of Theorem 3.36, which the paper uses only for the equality β_ℓ(G)=C(G;K_ℓ) in Theorem 4.9(1). The reader and stress-test are right: the base case omits j=mℓ for 2≤m<ℓ, and the induction step at j=ℓ^k sets G_{k+1}=G_k, which violates the distinctness requirement in Definition 3.1. These are genuine gaps, but they are repairable—the stress-test sketches explicit replacements, and they work. Because the equality with ℓ-particity is already known in the literature, this does not damage the central claim; it only weakens the paper's own proof of that equality.\n\nOne minor caveat: the arXiv text has corrupted displayed formulas, which made verification slower. Also, the introduction overstates prior interest in hom-complexity—this is a new invariant, so phrases like \"considerable interest\" are not backed by the cited literature.\n\nWho is this for? Any graph theorist working with covering numbers, homomorphisms, or chromatic-type parameters. The invariant gives a unified lens and the log formula is attractive. A serious referee should engage with it; the gaps in Theorem 3.36 are fixable.\n\nRecommendation: send it to review, with a request to repair Theorem 3.36 and tone down the intro.","headline":"A genuinely new invariant with a clean main formula; the proof of the ℓ-particity equality has repairable gaps, but the central result stands.","tokens_in":76,"tokens_out":1290,"would_cite":true,"duration_ms":44698,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","05C15","05C60","05C51","05C90"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper introduces hom-complexity C(G;H), the least number of distinct subgraphs needed to cover G so each maps to H, and proves that when the target has clique number equal to chromatic number, this quantity is the ceiling of the…","keywords":["hom-complexity","injective hom-complexity","graph homomorphism","chromatic number","clique number","covering number","ℓ-particity","bipartite dimension"],"falsifier":"Enumerate all pairs of distinct 3-partite subgraphs of K_6 (the case ℓ=3, j=6, which the paper's inductive decomposition does not cover) and check whether their union is all of K_6. A pair that works supports the claimed formula C(K_6;K_3)=2; a proof that no such pair exists would refute Theorem 4.9(1) for G=K_6.","tokens_in":25841,"feed_emoji":"🧩","tokens_out":10379,"duration_ms":86378,"temperature":0.7,"pith_summary":"The paper introduces a numerical invariant, C(G;H), that measures how far a pair of graphs is from admitting a graph homomorphism: it is the least k for which G can be written as the union of k distinct subgraphs, each of which maps into H by a homomorphism. The companion invariant IC(G;H) is defined the same way but requires the maps into H to be injective. The main result is that whenever the target H has clique number equal to chromatic number, C(G;H) equals the ceiling of the logarithm of χ(G) in base χ(H). That formula makes the invariant easy to compute for a broad class of targets and, as the paper shows, it subsumes known formulas for the ℓ-particity of a graph and for the bipartite dimension of a complete graph.","feed_headline":"Hom-complexity equals the log-ratio of chromatic numbers","feed_subtitle":"A new invariant counts how many subgraphs cover G while mapping into H; when ω(H)=χ(H), it is just a logarithm.","key_machinery":"The carrier of the argument is the hom-complexity C(G;H), defined in Definition 3.1 as the least k for which there are k distinct subgraphs G_1,...,G_k of G with G=G_1∪...∪G_k and a homomorphism G_i→H for every i. Two estimates do the work. The lower bound (Theorem 3.26) is the product bound χ(G)≤∏_i χ(G_i)≤χ(H)^{C(G;H)}. The upper bound (Theorem 3.30) uses the clique number of the target: if χ(G)≤ω(H)^n then C(G;H)≤n, proved by reducing to complete graphs and decomposing K_j into n subgraphs each of which maps into K_i. For targets with ω(H)=χ(H) the two inequalities coincide, producing the exact logarithmic formula. A refinement (Theorem 3.36) builds the decomposing pieces explicitly as ℓ-partite subgraphs, which is what connects C(G;K_ℓ) to the covering parameter β_ℓ(G).","core_discovery":"The paper's central claim is Corollary 3.34: for simple graphs G and H with χ(G)≥2 and ω(H)=χ(H)≥2, C(G;H)=⌈log_{χ(H)} χ(G)⌉. Specializing the target to a complete graph gives C(G;K_ℓ)=⌈log_ℓ χ(G)⌉, and via Theorem 4.9 this number is also the ℓ-particity β_ℓ(G), the least number of ℓ-partite subgraphs whose edges cover G. For complete graphs, C(K_n;K_2)=d(K_n), the bipartite dimension of K_n, reproducing d(K_n)=⌈log_2 n⌉. The proof combines a lower bound χ(G)≤χ(H)^{C(G;H)} with an upper bound C(G;H)≤n whenever χ(G)≤ω(H)^n; when ω(H)=χ(H) the two bounds meet, and Theorem 3.36 shows the upper bound can be realized by an optimal cover whose pieces are ℓ-partite subgraphs.","pith_inferences":["Beyond the paper, one could test which targets H, beyond those with ω(H)=χ(H), satisfy C(G;H)=⌈log_{χ(H)} χ(G)⌉ for every G; the paper's triangle-free 11-vertex example already shows some high-chromatic triangle-free targets fail.","Because IC(G;K_2)=|E(G)|, the injective variant behaves like an edge-counting parameter; an extension would be to compare IC(G;H) with edge-covering parameters such as clique-covering number for arbitrary H, following the connection the paper starts in Proposition 4.5.","The explicit optimal quasi-homomorphisms from Theorem 3.36 give a concrete algorithm for covering a graph by ℓ-partite subgraphs; applying it to the disjoint-subset graph considered in Remark 5.2(3) and checking whether any cover beats the naive logarithmic bound would test the open question the paper poses there."],"forward_implications":["For every target H with ω(H)=χ(H), hom-complexity is determined solely by the two chromatic numbers: C(G;H)=⌈log_{χ(H)} χ(G)⌉.","The complete-graph target recovers the classical formula β_ℓ(G)=⌈log_ℓ χ(G)⌉ for ℓ-particity, and C(K_n;K_2)=d(K_n)=⌈log_2 n⌉ for bipartite dimension.","Because C(G;H)=1 exactly when G→H, the invariant is a graded measurement of non-homomorphism: larger values mean more subgraphs are needed before any piece can map to H.","The triangular inequality C(G;K)≤C(G;H)C(H;K) and the reduction to cores give general tools for bounding hom-complexity between arbitrary graphs.","Computing C(G;H) is NP-complete in general (via H-colouring), so the exact formula for ω(H)=χ(H) identifies a large class of cases where the invariant is easy to compute."],"supporting_citations":[{"why":"supplies the homomorphism framework and the chromatic-number product bound (Exercise 11, p. 36) used for the lower bound","marker":"[10]"},{"why":"is the source of the ℓ-particity formula β_ℓ(G)=⌈log_ℓ χ(G)⌉ that Theorem 4.9(1) recovers","marker":"[8]"},{"why":"is the source of the bipartite-dimension formula d(K_n)=⌈log_2 n⌉ recovered as C(K_n;K_2)","marker":"[4]"},{"why":"establishes NP-completeness of H-colouring, which the paper cites for the hardness of computing C(G;H)","marker":"[9]"},{"why":"provides the graph-covering terminology under which C(G;H) is identified as the H-covering number","marker":"[14]"},{"why":"gives the lower bound log_2(|V(G)|+1) on clique covering that the new bound in Proposition 4.7 improves","marker":"[6]"},{"why":"supplies the classical clique-covering upper bound used as comparison in the clique-covering section","marker":"[3]"}],"fun_headline_variants":["When ω=χ, hom-complexity is a simple log of chromatic numbers","New invariant C(G;H) counts subgraphs covering G that map to H","Hom-complexity: log-ratio of chromatic numbers under ω=χ","Hom-complexity unifies ℓ-particity and bipartite dimension"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of the upper bound asks us to accept that every complete graph K_j with $ℓ^{{k−1}}$≤j≤ℓ^k can be split into k different ℓ-partite subgraphs by the displayed inductive recipe; as written, that recipe omits cases where j is a multiple of ℓ and, at j=ℓ^k, reuses the same subgraph, which Definition 3.1 forbids.","fun_headline_variants_meta":{"raw":{"variants":["When ω=χ, hom-complexity is a simple log of chromatic numbers","New invariant C(G;H) counts subgraphs covering G that map to H","Hom-complexity: log-ratio of chromatic numbers under ω=χ","Hom-complexity unifies ℓ-particity and bipartite dimension"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001053,"raw_usage":{"total_tokens":4556,"prompt_tokens":1217,"completion_tokens":3339,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":833,"completion_tokens_details":{"reasoning_tokens":3254}},"tokens_in":833,"tokens_out":3339,"duration_ms":22616,"temperature":1.0,"reasoning_tokens":3254,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:01:28.646798+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all pairs of distinct 3-partite subgraphs of K_6 (the case ℓ=3, j=6, which the paper's inductive decomposition does not cover) and check whether their union is all of K_6. A pair that works supports the claimed formula C(K_6;K_3)=2; a proof that no such pair exists would refute Theorem 4.9(1) for G=K_6.","supporting_citations":[{"cited_title":"Graphs and homomorphisms (Vol","cited_arxiv_id":null,"evidence_quote":"supplies the homomorphism framework and the chromatic-number product bound (Exercise 11, p. 36) used for the lower bound"},{"cited_title":"Journal of Graph Theory, 1(2), 131-133 (1977)","cited_arxiv_id":null,"evidence_quote":"is the source of the ℓ-particity formula β_ℓ(G)=⌈log_ℓ χ(G)⌉ that Theorem 4.9(1) recovers"},{"cited_title":"C., & Hammer, P","cited_arxiv_id":null,"evidence_quote":"is the source of the bipartite-dimension formula d(K_n)=⌈log_2 n⌉ recovered as C(K_n;K_2)"},{"cited_title":"Journal of Combinatorial Theory, Series B, 48(1), 92-110 (1990)","cited_arxiv_id":null,"evidence_quote":"establishes NP-completeness of H-colouring, which the paper cites for the hardness of computing C(G;H)"},{"cited_title":"Discrete Mathematics, 345(8), 112884 (2022)","cited_arxiv_id":null,"evidence_quote":"provides the graph-covering terminology under which C(G;H) is identified as the H-covering number"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the lower bound log_2(|V(G)|+1) on clique covering that the new bound in Proposition 4.7 improves"},{"cited_title":"W., & Pósa, L.: The representation of a graph by set intersections","cited_arxiv_id":null,"evidence_quote":"supplies the classical clique-covering upper bound used as comparison in the clique-covering section"}],"review_version":1}