Fact-checked by Grok 2 weeks ago

Graph homomorphism

In , a is a f from the vertex set of a graph G to the vertex set of a graph H such that for every edge \{u, v\} in G, the image \{f(u), f(v)\} is an edge in H; the mapping preserves adjacency but need not be injective or surjective, and non-adjacent vertices in G may map to adjacent or non-adjacent vertices in H. This concept generalizes fundamental graph properties, such as , where a proper k-coloring of G corresponds exactly to a homomorphism from G to the K_k on k vertices, ensuring that adjacent vertices receive different colors. Homomorphisms also imply inequalities between graph invariants, including that the clique number \omega(G) \leq \omega(H) and the chromatic number \chi(G) \leq \chi(H). Graph homomorphisms induce a preorder on the class of graphs, where G \preceq H if there exists a homomorphism from G to H; this relation is reflexive and transitive, and the equivalence classes under mutual homomorphisms form a partial order known as the homomorphism order. Within each equivalence class, a unique (up to isomorphism) minimal graph called the core exists, which has no proper homomorphic image other than itself, and every endomorphism of a core is an automorphism. For instance, the core of any connected bipartite graph with at least one edge is the complete bipartite graph K_{1,1} (equivalent to K_2), while odd cycles form an infinite descending chain in the homomorphism order. In computational terms, the homomorphism problem—deciding whether a given graph G admits a homomorphism to a fixed target graph H—is solvable in polynomial time if H is bipartite or has a loop, but NP-complete otherwise, making it a cornerstone of constraint satisfaction problems and dichotomy theorems in complexity theory. Applications span network design, where homomorphisms model resource allocation like exam scheduling (mapping conflict graphs to period graphs), and theoretical computer science, including fine-grained complexity analyses parameterized by structural measures such as clique-width. Historically, László Lovász proved in 1967 that the numbers of homomorphisms from all finite graphs to a given graph G uniquely determine G up to isomorphism, highlighting their role in graph identification.

Basic Concepts

Definitions

A graph homomorphism from a graph G = (V(G), E(G)) to a graph H = (V(H), E(H)) is a f: V(G) \to V(H) that preserves adjacency, meaning that for every edge \{u, v\} \in E(G), the image \{f(u), f(v)\} \in E(H). This mapping preserves the structure of edges but does not require f to be injective or surjective, nor does it demand preservation of non-edges. Related variants include injective homomorphisms, which map vertices one-to-one and thus embed G as an of H if the homomorphism is strong (preserving non-adjacency as well). Surjective homomorphisms cover all vertices of H, while covering maps are surjective homomorphisms that are locally bijective, meaning the restriction of f to the neighborhood of each vertex in G is a bijection onto the neighborhood of its image in H. Two graphs G and H are homomorphically equivalent if there exist from G to H and from H to G. The existence of a homomorphism from G to H is denoted by G \to H. For example, every graph admits a homomorphism to the trivial graph K_1 (a single vertex with no edges), and the identity function on any graph is a homomorphism to itself. Graph colorings correspond to homomorphisms onto complete graphs, and cores represent minimal graphs within homomorphic equivalence classes.

Cores and retracts

A retract of a graph G is an induced subgraph H of G together with a graph homomorphism \rho: G \to H that acts as the identity map on the vertices of H. This means that for every vertex v \in V(H), \rho(v) = v, and edges in G are preserved under \rho into H. Retracts provide a way to identify minimal substructures within a graph that capture essential homomorphic properties. The core of a graph G, denoted G^\bullet, is defined as the unique (up to ) minimal graph that is homomorphically equivalent to G. Equivalently, it is the smallest retract of G such that there exists a from G to G^\bullet and vice versa, with G^\bullet having no proper retract of its own. Every finite possesses a core, which serves as a canonical representative of its homomorphism equivalence class. Cores exhibit several key properties that highlight their minimality and uniqueness. For any graph G, the core G^\bullet is a retract of G, and any graph homomorphically equivalent to G also retracts to G^\bullet. Moreover, cores are minimal in the sense that no proper subgraph of a core admits a homomorphism from the core itself while remaining a retract. This ensures that within each equivalence class under homomorphic equivalence, the core is the unique smallest member up to isomorphism. Representative examples illustrate these concepts. Complete graphs K_n (for n \geq 1) are their own cores, as any homomorphism from K_n to a proper subgraph would fail to preserve the complete set of edges without violating the identity condition on the subgraph. Similarly, odd cycles C_{2k+1} (for k \geq 1) serve as cores, particularly for graphs without bipartite substructures, since no proper retract exists due to the odd girth preventing reduction. In contrast, any connected with at least one edge has K_2 (the single-edge graph) as its core, reflecting their 2-colorability and homomorphism to this minimal connected bipartite structure. To compute the core of a finite G, one can iteratively apply retractions: start with G and repeatedly find and retract to proper retracts until no further proper retract exists. Since each retraction strictly reduces the number of vertices or edges in finite graphs, this process terminates in finitely many steps, yielding the core. A fundamental states that every finite G is homomorphically equivalent to its core G^\bullet, and the cores fully characterize the homomorphism equivalence classes of graphs. This equivalence implies that testing homomorphisms between graphs can often be reduced to their cores, providing a structural invariant for .

Connections to Graph Coloring

Standard colorings

A proper k-coloring of a graph G assigns colors from a set of size k to the vertices of G such that no two adjacent vertices share the same color. This is equivalent to a from G to the Kk, where the vertices of Kk represent the k colors, and edges exist between all pairs of distinct vertices to ensure adjacent vertices in G map to distinct colors. Conversely, any homomorphism from G to Kk induces a proper k-coloring of G, as the mapping preserves adjacency and the complete structure of the target prevents monochromatic edges. The chromatic number χ(G), defined as the smallest number of colors needed for a proper coloring of G, corresponds directly to the smallest k such that a homomorphism G → Kk exists. Thus, if there is a from G to Kk, then χ(G) ≤ k; if χ(G) > k, no such homomorphism exists. This connection highlights how graph generalize coloring problems, with the target capturing the standard notion of proper vertex coloring. Brooks' , which states that for a connected graph G that is neither complete nor an odd cycle, χ(G) ≤ Δ(G) (the maximum ), implies that such graphs admit a homomorphism to KΔ(G), a (Δ(G)-1)-; exceptions like odd cycles and complete graphs, where χ(G) = Δ(G) + 1, require Δ(G) + 1 colors and thus do not admit a homomorphism to KΔ(G). Precoloring extension problems arise when a partial coloring is given on a of vertices, and one seeks to extend it to a full proper k-coloring. In homomorphism terms, this requires a from G to Kk that maps the precolored vertices to their specified color vertices in the target, effectively fixing their images while ensuring the mapping preserves edges. For instance, bipartite graphs, which are 2-colorable, always admit a to K2 (the on two vertices, isomorphic to a single edge), as their vertices can be partitioned into two sets mapped to the two endpoints; this includes even cycles and . In contrast, odd cycles, being non-bipartite, have chromatic number 3 and do not homomorph to K2, as any such mapping would force an odd-length to connect the two target vertices without violating adjacency preservation.

Coloring variants

List colorings generalize proper vertex colorings by assigning to each vertex v a list L(v) of allowable colors, with a proper list coloring requiring that adjacent vertices receive distinct colors from their respective lists. This variant can be reformulated using graph homomorphisms by constructing a target graph whose vertices correspond to the possible colors in the lists, with edges between vertices representing incompatible color choices for adjacent graph vertices; a homomorphism from the original graph to this target then corresponds to a valid list coloring. The choice number, or list chromatic number, \mathrm{ch}(G), introduced by Erdős, Rubin, and Taylor, is the smallest integer k such that G admits a proper coloring from any list assignment where |L(v)|=k for all v \in V(G). In the broader framework of list H-coloring, where H is a fixed target graph encoding color constraints, the problem determines whether G homomorphs to H respecting prescribed lists of target vertices for each source vertex; this generalization was systematically studied by Feder and Hell, revealing polynomial-time solvability for certain reflexive H. Circular colorings extend standard colorings by arranging colors on a circle, allowing adjacent vertices to receive colors that are sufficiently separated angularly rather than entirely distinct. The circular chromatic number \chi_c(G) is defined as the infimum of all r > 0 such that G admits a homomorphism to a circular complete graph G(n,r) for some integer n > 2r, where G(n,r) has vertex set \{0,1,\dots,n-1\} and edges between distinct vertices i,j if the circular distance d(i,j) = \min(|i-j|, n - |i-j|) \geq r. Equivalently, for rational r = p/q in lowest terms with p > 2q, this corresponds to a homomorphism to the q-th power of the cycle C_p, where edges connect vertices at graph distance at most q along the cycle. Introduced by Vince under the name star chromatic number, \chi_c(G) satisfies \chi(G)-1 < \chi_c(G) \leq \chi(G), providing a refinement that captures fractional aspects of coloring while preserving the homomorphism structure for non-complete targets. Zhu further connected this to list homomorphisms for circular arc graphs, showing dichotomy results for solvability. Fractional colorings relax the integer constraints of standard colorings by allowing vertices to receive distributions over colors, leading to the fractional chromatic number \chi_f(G), which is the infimum of t > 0 such that the vertices of G can be covered by t weighted independent sets (with total weight 1 per vertex). This parameter arises as the optimal value of the of the integer linear program for chromatic number and equals the minimum t such that there exists a fractional homomorphism from G to the K_t, interpreted as a on the set of all homomorphisms to K_t that preserves edges in . In the context of dense graph limits, \chi_f(G) relates to homomorphic densities, where for a representing G, it bounds the supremum over cliques K of the homomorphism density t(G,K)/|V(K)|, providing asymptotic approximations for large graphs. This connection highlights how homomorphisms extend to fractional settings via convex combinations, bridging combinatorial and analytic . Nešetřil and Ossona de Mendez established bounds using power graphs and densities, linking fractional parameters to homomorphism orders. Oriented colorings address asymmetries in graphs by considering homomorphisms to oriented graphs (s without bidirectional edges), particularly . The oriented chromatic number \chi_o([G](/page/G)) of an undirected [G](/page/G) is the smallest k such that [G](/page/G) admits an orientation \overrightarrow{[G](/page/G)} with a to some k-vertex T_k. Equivalently, it is the minimum order of an oriented H (without symmetric edges) such that [G](/page/G) to H. This parameter, explored by Sopena, generalizes the chromatic number to directed settings, with \chi([G](/page/G)) \leq \chi_o([G](/page/G)) \leq (2\chi([G](/page/G))-1)!! for some , and remains bounded by 80 for planar . The dichromatic number \overrightarrow{\chi}(D) for a D, introduced by Neumann-Lara, is the smallest k such that V(D) partitions into k acyclic induced subs, and for undirected [G](/page/G), it equals the maximum dichromatic number over all orientations of [G](/page/G); to transitive characterize low dichromatic numbers. These variants capture directionality constraints absent in undirected colorings. Hadwiger's conjecture, asserting that every G without a K_t- has chromatic number at most t-1, admits a reformulation in homomorphism terms: every minor-closed family of graphs contains an element maximal with respect to the homomorphism order (where G \preceq H if G homomorphs to H). This equivalence, established by Naserasr and Nigussie, underscores how minor structure influences homomorphism preservation and coloring bounds. Regarding choice numbers, while \mathrm{ch}(G) \geq \chi(G) always holds, specific classes exhibit tight relations; for instance, it is conjectured for claw-free graphs that \mathrm{ch}(G) = \chi(G), and proven equal in subclasses like line graphs of bipartite graphs. In general, \mathrm{ch}(G) \leq \chi(G) + 1 holds for certain structured graphs, such as those with bounded , reflecting localized homomorphism properties.

Orientations without long paths

The Gallai–Hasse–Roy–Vitaver establishes a fundamental connection between the chromatic number of an undirected and the orientations of its edges. Specifically, a G is k-colorable if and only if there exists an orientation of G in which every directed path has length at most k-1. This result was independently discovered by several researchers: Vitaver in 1962 using Boolean matrix powers to characterize minimal colorings, Hasse in 1964/65 through algebraic foundations of , Roy in 1967 by relating chromatic numbers to longest paths in orientations, and Gallai in 1968 via directed paths and circuits. Equivalently, the theorem implies that G admits a to the transitive T_k, which is the K_k oriented as a transitive (with vertices ordered $1 < 2 < \cdots < k and arcs from lower to higher indices), since such a homomorphism preserves the path length bound. Acyclic orientations, which contain no directed cycles and thus no infinite paths, relate closely to homomorphisms to transitive closures of partial orders. Every undirected graph admits an acyclic orientation, obtained by linearly ordering the vertices and directing edges from earlier to later positions. In particular, bipartite graphs, being 2-colorable, possess orientations where the maximum directed path length is 1, such as directing all edges from one partite set to the other; this corresponds to a homomorphism to the directed edge (transitive tournament T_2). More generally, the existence of a kernel in a digraph—an independent set that reaches every other vertex via a directed path—is guaranteed for acyclic digraphs, as one can select vertices with no outgoing arcs iteratively; this property underscores the structural simplicity induced by acyclicity and ties back to homomorphism targets without cycles. The theorem's converse ensures that if a graph family admits no homomorphism to any digraph containing a directed path of length exceeding some fixed m, then every orientation of graphs in the family has maximum directed path length at most m, bounding their chromatic numbers by m+1. Extensions to oriented colorings consider homomorphisms to oriented graphs (antisymmetric digraphs) without long directed paths; for instance, the oriented chromatic number of a graph is the minimum order of an oriented graph target without certain forbidden structures, generalizing the path-length duality to asymmetric edge directions. As an example, complete graphs K_n require orientations with directed paths of length up to n-1 in every case, reflecting their chromatic number n and the guaranteed Hamiltonian path in any tournament orientation.

Links to Constraint Satisfaction Problems

Application examples

Graph homomorphisms find practical application in scheduling problems, such as assigning courses or exams to time slots while respecting constraints like avoiding consecutive days for related classes. In this setup, the source represents courses as vertices with edges indicating conflicts (e.g., shared students), and the target graph is the complement of a , where vertices denote time slots and edges connect non-adjacent slots to enforce the no-consecutive-days rule. A maps courses to permissible slots without mapping conflicting pairs to adjacent slots, ensuring feasible schedules. In frequency assignment for radio transmitters, s model the allocation of channels to avoid in wireless s. The graph has vertices for transmitters and edges for pairs that could interfere based on proximity or signal overlap; the target graph represents available frequencies, with edges between compatible frequencies (e.g., sufficiently separated to prevent overlap). A homomorphism assigns frequencies such that interfering transmitters map to adjacent (compatible) frequencies, minimizing reuse conflicts and optimizing spectrum use. This approach extends to allocation in communication s, where homomorphisms capture signal constraints by mapping network nodes to segments, ensuring adjacent nodes receive non-overlapping allocations to maintain . Social network analysis employs to map user interactions onto compatibility or role for grouping and tasks. in the source represent users, with edges denoting relationships like friendships; the target encodes group structures or roles, where a homomorphism preserves connections to identify clusters (e.g., communities with similar interaction patterns). This facilitates , such as predicting user attributes, by leveraging homomorphism densities from sampled motifs in datasets like Facebook100, achieving high accuracy in distinguishing network types (e.g., AUC scores up to 0.969 for ). Specific examples include Sudoku puzzles, which can be modeled as constraint satisfaction problems related to graph homomorphisms, enforcing Latin square constraints through no repetitions in rows, columns, or 3x3 blocks. Solving the puzzle corresponds to finding a valid assignment that satisfies these constraints, often using constraint propagation techniques. Register allocation in compilers also relies on graph homomorphisms via the special case of graph coloring. The interference graph has vertices for program variables or temporaries, with edges for pairs live simultaneously; a homomorphism to a complete graph K_k (where k is the number of registers) assigns registers such that interfering variables map to distinct vertices, preventing overlaps during execution. This approach, foundational in optimizing code, balances register use with spilling to memory when k-colorings are infeasible.

Formal correspondence

In the (CSP) framework, graphs are viewed as relational structures consisting of a domain (the set) and relations (the edge sets). A graph homomorphism from a source graph G to a target graph H corresponds precisely to an instance of the CSP denoted CSP(H), where the variables are the vertices of G, the domain is the set of H, and the are imposed by the edges of G, requiring that adjacent vertices in G map to adjacent vertices in H. This equivalence establishes graph homomorphisms as a fundamental subclass of CSPs, where the language is defined by the relations of H. From the perspective of universal algebra, graph homomorphisms can be analyzed through polymorphisms, which are operations on the vertex set of H that preserve its relations. A polymorphism of H is a function that maps tuples in the relations of H to tuples also in those relations, and the algebra associated with H—its template—encapsulates the constraint language for CSP(H). This algebraic structure determines the computational properties of the homomorphism problem, such as solvability via local consistency methods when certain polymorphisms (e.g., totally symmetric idempotent operations) are present. In the context of the Feder-Vardi dichotomy conjecture, graph homomorphism problems represent a special case of CSPs restricted to a single binary relation type per edge in H, which was resolved affirmatively: for any finite directed graph H, deciding the existence of a homomorphism to H is either solvable in polynomial time or NP-complete. The formal correspondence extends to reductions between general binary CSPs and graph homomorphism problems. Any binary CSP instance reduces in polynomial time to a graph homomorphism problem via gadget constructions that encode the binary constraints as edges in an auxiliary . Conversely, graph homomorphism problems reduce to binary CSPs through interpretations or bi-interpretations of relational structures, preserving the . This mutual reducibility positions the graph homomorphism problem as the canonical NP-complete problem within the class of binary CSPs, serving as a for results in .

Structural Properties

Homomorphism orders

The homomorphism relation → on the class of all finite undirected graphs defines a , as it is reflexive via the identity mapping and transitive via of homomorphisms. Two graphs are homomorphically equivalent if each maps to the other, yielding an ≡ whose quotient forms a under the induced order, known as the homomorphism order on graphs. This poset is universal, embedding every countable partial order as a subposet. The homomorphism order possesses lattice structure: the set of equivalence classes forms a distributive lattice, with the join of classes [G] and [H] given by the class of the G + H (since any graph mapping to both maps to their union), and the meet by the class of the homomorphic product G × H (where vertices are pairs from G and H, with edges between pairs if both components are adjacent). This lattice is dense, meaning that if [G] < [H] (i.e., G → H but not H → G), then there exists [K] with [G] < [K] < [H], except in trivial cases such as when G is edgeless. In , graph homomorphisms form the morphisms in the of graphs, with graphs as objects; this category admits forgetful functors to the (forgetting structure) and supports further structure-preserving maps to relational structures. Fixed-point theorems arise in this context, notably through the existence of cores—minimal graphs in each where every is an —providing fixed points for retraction operators in the order. Additionally, order ideals in the homomorphism poset correspond to hereditary graph classes, facilitating applications of homomorphism densities in , such as bounds via the on subgraph counts in dense graphs. A representative example is the total order on complete graphs: K_m → K_n if and only if m ≤ n, since any homomorphism maps cliques to cliques of at most equal size, forming a chain in the poset.

Incomparable graphs

In graph theory, two graphs G and H are incomparable under the homomorphism order if there exists neither a homomorphism from G to H nor from H to G. This relation highlights the partial ordering nature of the homomorphism poset, where comparability requires preservation of structural properties such as chromatic number and odd girth. Specifically, for G \to H to hold, the chromatic number satisfies \chi(G) \leq \chi(H) and the odd girth satisfies \mathrm{og}(G) \geq \mathrm{og}(H), conditions that fail bidirectionally for incomparable pairs. A classic example of incomparable graphs is the Grötzsch graph G_G and the K_3. The Grötzsch graph is triangle-free with \chi(G_G) = 4 and \mathrm{og}(G_G) = 5, so it admits no to K_3 (which has \chi(K_3) = 3), while K_3 admits no to G_G due to the latter's triangle-free structure. An in the order is a set (maximal or otherwise) of pairwise incomparable graphs, playing a key role in forbidden characterizations through connections to homomorphism dualities. A duality pair \langle F, D \rangle partitions the poset such that graphs homomorphic to D are precisely those avoiding subgraphs in F, and maximal s underpin such characterizations by enabling infinite extensions of these forbidden structures. For instance, splitting maximal s—those partitionable into subsets B and C covering the poset via upsets and downsets—facilitate duality-based descriptions of graph classes defined by constraints. Incomparability underscores fundamental trade-offs in graph parameters, particularly between odd girth and chromatic number, where graphs optimizing one often sacrifice the other, preventing universal comparability. The homomorphism order's partiality implies no single linear extension captures all relations canonically, complicating global classifications. A notable structural result is the existence of infinite antichains; the Mycielski graphs S_k (for odd k \geq 3), which are triangle-free with \chi(S_k) = k and increasing odd girth, form such an antichain, as S_k \not\to S_\ell for k \neq \ell due to chromatic mismatches and girth obstructions.

Computational Complexity

General decision problem

The general for graph homomorphisms asks whether there exists a homomorphism from a given source G to a given target H. This problem is a fundamental question in and , capturing various restricted cases such as when H is a . The problem lies in NP, as a nondeterministic algorithm can guess a function f: V(G) \to V(H) as a certificate and verify it in polynomial time by checking, for every edge \{u, v\} \in E(G), that \{f(u), f(v)\} \in E(H); this verification requires O(|E(G)|) time after guessing the O(|V(G)|)-sized mapping. Membership in NP follows directly from this polynomial-time verifiable certificate structure. The problem is NP-hard in general. A key reduction is from the graph k-coloring problem, which is NP-complete for k \geq 3: given a graph G' and integer k \geq 3, G' is k-colorable if and only if there is a homomorphism from G' to the complete graph K_k. Thus, setting H = K_k reduces k-coloring to the homomorphism problem. The NP-completeness of k-coloring itself follows from a reduction from 3-SAT via gadgets that enforce color distinctions for literals and clauses. Another source of hardness arises from the injective homomorphism variant, which requires the mapping to be one-to-one on vertices; this specializes to the NP-complete subgraph isomorphism problem (finding if H embeds injectively into G) by considering induced subgraphs and edge preservations under injection. In parameterized complexity, the problem is W-hard when parameterized by the solution size, interpreted as the size of the target graph |V(H)|. This follows because, for parameter value 3 (i.e., H = K_3), the problem reduces to 3-coloring, which is NP-complete and thus para-NP-hard; any para-NP-complete problem is W-hard under fpt-reductions. The NP-completeness of the general graph homomorphism decision problem was established in the 1970s through these reductions from known NP-complete problems like graph coloring, with comprehensive listings appearing in standard references on computational complexity.

Dichotomy for fixed target graphs

In the case where the target graph H is fixed, the of deciding whether a given input graph G admits a to H—known as the H-coloring problem—exhibits a clean dichotomy for undirected graphs. The Hell–Nešetřil theorem states that for undirected graphs, this problem is solvable in polynomial time if H is bipartite or contains a ; otherwise, it is NP-complete. The polynomial-time cases are as follows. If H contains a , then for any input G, a constant mapping of all vertices of G to the looped vertex in H is a homomorphism, as edges in G map to the loop (an edge) and non-edges may map to edges. Thus, the problem is trivially solvable in constant time by always answering yes. If H is bipartite (and loopless), the problem allows a reduction to 2-SAT: vertices of G can be assigned to the partitions of H via implications that enforce adjacency constraints, solvable efficiently using graph-based algorithms for 2-SAT. For the NP-hardness when H is non-bipartite and loopless, the proof constructs a reduction from 3-SAT using gadgets based on odd cycles in H, which force inconsistent assignments in satisfiable instances while preserving homomorphisms for unsatisfiable ones. This dichotomy extends to directed graphs, where the full classification was resolved algebraically in 2017. Independently, Bulatov and Zhuk proved that, for a fixed directed graph H, the homomorphism problem is polynomial-time solvable if the core of H admits a polymorphism algebra with a weak near-unanimity function (or more generally, satisfies certain tractable relational properties under the algebraic theory of CSPs); otherwise, it is NP-complete. These results confirm the dichotomy conjecture for constraint satisfaction problems restricted to graph homomorphisms, leveraging polymorphisms to characterize tractability without enumerating cases. Special cases include trivial target graphs H with a universal sink or source (e.g., a single vertex with loops), where the problem is always polynomial-time due to constant-time verification. As of , no significant revisions to these dichotomies have emerged, solidifying their role in confirming the general CSP dichotomy for finite-domain graph homomorphism instances.

Complexity for fixed source families

In the variant of the graph homomorphism problem considered here, the source graph G is restricted to belong to a fixed family \mathcal{F} of graphs, while the target graph H is part of the input. The task is to determine whether there exists a homomorphism from G to H. A fundamental result classifies the of this problem based on structural properties of \mathcal{F}. Specifically, assuming FPT \neq W, the problem is solvable in polynomial time if and only if the cores of the graphs in \mathcal{F} have bounded . The of a graph is its minimal homomorphic retract, unique up to . When the cores have bounded , the problem reduces to evaluating a monadic formula on a decomposition of the core, which can be done efficiently using Courcelle's theorem. This yields a polynomial-time whose running time depends only on the bound on the and the of the structures. Conversely, if the cores have unbounded , the problem is NP-hard. Classes of graphs with bounded expansion provide another perspective on tractability, though they generally do not imply bounded . Such classes, defined by a bound on the density of shallow minors, admit polynomial-time algorithms for homomorphism-related tasks via sparse graph techniques, including low colorings and neighborhood complexity bounds that facilitate efficient enumeration or duality checks. However, for the full with arbitrary H, these classes often lead to unless additional restrictions apply. Examples illustrate these boundaries. The family of all planar graphs has bounded expansion but unbounded treewidth in its cores, rendering the homomorphism problem NP-complete; for instance, when H = K_3, it reduces to 3-coloring planar graphs, which is NP-complete. More generally, minor-closed families exhibit bounded expansion but typically unbounded (except in degenerate cases like paths or trees), leading to NP-completeness. In contrast, families whose cores have bounded , such as series-parallel graphs, admit polynomial-time solutions. For the unrestricted family of all graphs, the problem is NP-complete.