(Injective) hom-complexity between graphs

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 $\ddot{I}‡$ and clique number $\ddot{I}‰$. We provide the formula \[\text{C}(G;H)=\lceil\log_{χ(H)}χ(G)\rceil\] whenever $\ddot{I}‰(H)=\ddot{I}‡(H)$. For example, we obtain $\text{C}(G;K_{\ell })=\lceil {\log }_{\ell }\ddot{I}‡(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 ${\hat{I}}_{\ell }^2(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 ${\hat{I}}_{\ell }^2(G)=\lceil {\log }_{\ell }\ddot{I}‡(G)\rceil$ and $\mathrm{d}(K_n)=\lceil {\log }_{2}n\rceil$.

33 pages. It is a completely new version which is pitched more clearly at the readership and direction of some specific journal. We also discuss a connection between the (injective) hom-complexity and several well-known covering numbers. Comments are welcome