Pith. sign in

REVIEW 2 major objections 5 minor 18 references

(Injective) hom-complexity between graphs

T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read 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…

desk verdict A genuinely new invariant with a clean main formula; the proof of the ℓ-particity equality has repairable gaps, but the central result stands. read the letter →

arxiv 2411.16547 v3 pith:PEHHCVJ5 submitted 2024-11-25 math.CO

Cesar A. Ipanaque Zapata , Josué A. Aguirre Enciso , Wilman Francisco Cuba Ramos This is my paper · ORCID
classification math.CO MSC 05C2005C1505C6005C5105C90
keywords hom-complexityinjectivegraphhomomorphismchromaticnumbercliquecoveringℓ-particitybipartitedimension
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

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.

What carries the argument

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).

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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.

Referee Report

2 major / 5 minor

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.

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 (2)
  1. [Theorem 3.36(1)] 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.
  2. [Theorem 3.36(1), induction step at j = ℓ^k] 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.
minor comments (5)
  1. [Abstract and Section 2] The abstract contains the malformed string '\aspas{complexity}', and Section 2 contains the typo 'homomorphsims' in the definition of homomorphisms.
  2. [Proposition 3.28] 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).
  3. [Remark 3.16] 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.
  4. [Definition 3.1 and abstract] 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.
  5. [Example 3.19] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: Corollary 3.34 is derived from independent lower and upper bounds; self-citations are peripheral.

full rationale

The central formula C(G;H)=ceil(log_{chi(H)} chi(G)) for omega(H)=chi(H) is derived from two independent ingredients: Theorem 3.26, which uses the standard product inequality for chromatic numbers (Proposition 2.3) to give the lower bound, and Proposition 3.28/Theorem 3.30, which gives the upper bound by explicitly decomposing K_j into i-colourable subgraphs and using monotonicity under homomorphisms (Theorem 3.8). Neither ingredient assumes the target formula. Corollary 3.34 then combines the two bounds; the equality with known covering numbers in Theorem 4.9 is an additional identification, not a premise. The only self-citations are [2] (the third author's thesis, mentioned as containing a previous version of the notion) and [17] (used only in Remark 4.12 to compare with sectional number); neither is load-bearing for the main theorem. The proof of Theorem 3.36 has a repairable gap concerning omitted multiples of ell and a reused subgraph at j=ell^k, but that is a correctness issue in an auxiliary construction, not a circular step, since the lower and upper bounds for Corollary 3.34 do not depend on that theorem. The paper also independently recovers known formulas such as beta_ell(G)=ceil(log_ell chi(G)) and d(K_n)=ceil(log_2 n), rather than assuming them as inputs. No circularity pattern is present.

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

No free parameters are fitted; no external empirical constants. The paper introduces a graph invariant, not a physical entity. The main claims rest on standard graph theory and on the cited covering-number definitions; no ad hoc axioms beyond the definitions are introduced.

assumptions (6)
  • standard math Standard facts about graph homomorphisms: G→H implies χ(G)≤χ(H), and a k-colouring is a vertex-surjective homomorphism to K_k
    Invoked throughout Section 2 and in the lower bound Theorem 3.26; sourced from [10].
  • standard math Product bound for chromatic numbers of a cover: χ(G) ≤ ∏_j χ(G_j) when G=∪G_j
    Proved as Proposition 2.3 using [10, Exercise 11]; it underpins the lower bound and therefore the main formula.
  • standard math Every finite graph has a unique core and retractions exist, and hom-complexity is invariant under replacing a graph by its core
    Used in Proposition 3.12 and Example 3.13; standard from [10].
  • domain assumption The graphs treated are finite, or the invariants are interpreted with infinities, so minima over k and chromatic numbers are meaningful
    The paper never states finiteness; without it C(G;H)=∞ or χ(G) may be undefined for infinite graphs.
  • standard math H-colouring is NP-complete for non-bipartite H (Hell and Nešetřil)
    Used only to argue that computing C(G;H) is NP-complete in general; not used in the main bounds.
  • domain assumption The covering numbers βℓ(G) and dℓ(G) from Definition 4.4 are the standard edge-covering numbers from [8] and [4]
    Needed for Theorem 4.9 and Proposition 4.11; the paper's goal is to show C coincides with them.

how reviews work

0 comments
Cite this review

Pith. "Pith review of (Injective) hom-complexity between graphs." pith.science (2026). https://pith.science/paper/PEHHCVJ5

@misc{pith2026241116547,
  author       = {Pith},
  title        = {Pith review of: (Injective) hom-complexity between graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PEHHCVJ5}},
  note         = {Machine review of arXiv:2411.16547}
}
abstract

We present the notion of hom-complexity, $\text{C}(G;H)$, for two graphs $G$ and $H$, along with basic results for this numerical invariant. This invariant $\text{C}(G;H)$ is a number that measures the \aspas{complexity} of the question: when is there a homomorphism $G\to H$? More precisely, $\text{C}(G;H)$ is the least positive integer $k$ such that there are $k$ different subgraphs $G_j$ of $G$ such that $G=G_1\cup\cdots\cup G_k$, and for each $G_j$, there is a homomorphism $G_j\to H$. Likewise, we introduce the notion of injective hom-complexity, $\text{IC}(G;H)$. The (injective) hom-complexity is a graph invariant. Additionally, these invariants can be used to show the nonexistence of homomorphisms. We explore the sub-additivity of (injective) hom-complexity and study products. We describe bounds for the hom-complexity in terms of chromatic number $\chi$ and clique number $\omega$. We provide the formula \[\text{C}(G;H)=\lceil\log_{\chi(H)}\chi(G)\rceil\] whenever $\omega(H)=\chi(H)$. For example, we obtain $\text{C}(G;K_\ell)=\lceil\log_{\ell}\chi(G)\rceil$. Moreover, we discuss a connection between the (injective) hom-complexity and several well-known covering numbers. For instance, we provide a lower bound for the clique covering number in terms of the injective hom-complexity. Additionally, we show that the hom-complexity $\mathrm{C}(G;K_{\ell})$ coincides with the $\ell$-particity $\beta_\ell(G)$ of $G$, and the hom-complexity $\mathrm{C}(K_n;K_{2})$ coincides with the bipartite dimension $\mathrm{d}(K_n)$ of $K_n$. As a consequence, we recover the well-known formulas $\beta_\ell(G)=\lceil\log_{\ell}\chi(G)\rceil$ and $\mathrm{d}(K_n)=\lceil\log_{2}n\rceil$.

Figures

Figures reproduced from arXiv: 2411.16547 by the authors.

Figure 1
Figure 1. The graphs G and H. We find that χ(G) = 4 and ω(H) = χ(H) = 3, leading to the conclusion that C(G; H) = 2 (see Corollary 3.34). Designing an optimal quasi-homomorphism from G to H is greatly simplified by following two main steps: S1. First, we obtain an optimal quasi-homomorphism from K4 to K3. S2. Next, we design an optimal quasi-homomorphism from G to H. In Step S1, we utilize the proof of Proposition 3.28. Here,… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    N.: Complexes of graph homomorphisms

    Babson, E., & Kozlov, D. N.: Complexes of graph homomorphisms. Israel Journal of Mathematics, 152, 285-312 (2006)

    work page 2006

  2. [2]

    F.: Topología del problema de migración de datos

    Cuba Ramos, W. F.: Topología del problema de migración de datos. Ph.D. thesis (in Spanish), FCM, UNMSM, Perú (2023)

    work page 2023

  3. [3]

    W., & Pósa, L.: The representation of a graph by set intersections

    Erdös, P., Goodman, A. W., & Pósa, L.: The representation of a graph by set intersections. Canadian Journal of Mathematics, 18, 106-112 (1966)

    work page 1966

  4. [4]

    C., & Hammer, P

    Fishburn, P. C., & Hammer, P. L.: Bipartite dimensions and bipartite degrees of graphs. Discrete Mathematics, 160(1-3), 127-148 (1996)

    work page 1996

  5. [5]

    A., & Pullman, N

    Gregory, D. A., & Pullman, N. J.: On a clique covering problem of Orlin. Discrete Math- ematics, 41(1), 97-99 (1982)

    work page 1982

  6. [6]

    Gyárfás, A.: A simple lower bound on edge coverings by cliques. Discret. Math., 85(1), 103-104 (1990) (INJECTIVE) HOM-COMPLEXITY BETWEEN GRAPHS 33

    work page 1990

  7. [7]

    Annals of the New York Academy of Sciences, 175(1), 198-205 (1970)

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

    work page 1970

  8. [8]

    Journal of Graph Theory, 1(2), 131-133 (1977)

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

    work page 1977

Show all 18 references
  1. [9]

    Journal of Combinatorial Theory, Series B, 48(1), 92-110 (1990)

    Hell, P., & Nešetřil, J.: On the complexity of H-coloring. Journal of Combinatorial Theory, Series B, 48(1), 92-110 (1990)

    1990

  2. [10]

    Graphs and homomorphisms (Vol

    Hell, P., & Nešetřil, J. Graphs and homomorphisms (Vol. 28). Oxford University Press (2004)

    2004

  3. [11]

    A.: Data migration: Need, strategy, challenges, methodology, categories, risks, uses with cloud computing, and improvements using suggested proposed Model (DMig1)

    Hussein, A. A.: Data migration: Need, strategy, challenges, methodology, categories, risks, uses with cloud computing, and improvements using suggested proposed Model (DMig1). Journal of Information Security, 12, 79-103 (2021)

    2021

  4. [12]

    Journal of Combina- torial Theory, Series A, 25(3), 319-324 (1978)

    Lovász, L.: Kneser’s conjecture, chromatic number, and homotopy. Journal of Combina- torial Theory, Series A, 25(3), 319-324 (1978)

    1978

  5. [13]

    In Indagationes Mathematicae (Proceedings) (Vol

    Orlin, J.: Contentment in graph theory: covering graphs with cliques. In Indagationes Mathematicae (Proceedings) (Vol. 80, No. 5, pp. 406-424). North-Holland (1977)

    1977

  6. [14]

    Discrete Mathematics, 345(8), 112884 (2022)

    Schwartz, S.: An overview of graph covering and partitioning. Discrete Mathematics, 345(8), 112884 (2022)

    2022

  7. [15]

    I.: Functorial data migration

    Spivak, D. I.: Functorial data migration. Information and Computation, 217, 31-51 (2012)

    2012

  8. [16]

    B.: Introduction to graph theory (Vol

    West, D. B.: Introduction to graph theory (Vol. 2). Upper Saddle River: Prentice hall (2001)

    2001

  9. [17]

    Zapata, C. A. I., & Ramos, W. F. C.: Número seccional de un homomorfismo de grafos. Pesquimat, 26(2), 39-46 (2023)

    2023

  10. [18]

    H., Imrich, W., & Klavžar, S.: Handbook of product graphs (Vol

    Hammack, R. H., Imrich, W., & Klavžar, S.: Handbook of product graphs (Vol. 2). Boca Raton: CRC press (2011) (C. A. Ipanaque Zapata)Departamento de Matemática - IME-USP, Caixa Postal 66281 - Ag. Cidade de São Paulo, CEP: 05314-970 - São Paulo - SP - Brasil Email address: cesar...

    2011

Pith tools

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