# On the complexity of H-coloring

@article{Hell1990OnTC, title={On the complexity of H-coloring}, author={Pavol Hell and Jaroslav Nesetril}, journal={J. Comb. Theory, Ser. B}, year={1990}, volume={48}, pages={92-110} }

Abstract Let H be a fixed graph, whose vertices are referred to as ‘colors’. An H-coloring of a graph G is an assignment of ‘colors’ to the vertices of G such that adjacent vertices of G obtain adjacent ‘colors’. (An H-coloring of G is just a homomorphism G → H). The following H-coloring problem has been the object of recent interest: Instance: A graph G. Question: Is it possible to H-color the graph G?
H-colorings generalize traditional graph colorings, and are of interest in the study of… Expand

#### Figures and Topics from this paper

#### 724 Citations

Exact Algorithms for Graph Homomorphisms

- Mathematics, Computer Science
- Theory of Computing Systems
- 2007

It is shown that for an odd integer $k\ge 5$, whether an input graph G with n vertices is homomorphic to the cycle of length k, can be decided in time, which is the first NP-hard case different from graph coloring. Expand

Exact Algorithms for Graph Homomorphisms

- Mathematics, Computer Science
- FCT
- 2005

It is shown that, for a given graph G on n vertices and an odd integer k≥ 5, whether G is homomorphic to a cycle of length k can be decided in time min, which is the first NP-hard case different from graph coloring. Expand

Generalized H-Coloring of Graphs

- Mathematics, Computer Science
- ISAAC
- 2000

For fixed simple graph H and subsets of natural numbers σ and ρ, (H, σ, ρ)-colorings are introduced as generalizations of H-colorings of graphs and the study of how these colorings are related is initiated. Expand

Hereditarily hard H-colouring problems

- Computer Science, Mathematics
- Discret. Math.
- 1995

A conjecture is made as to precisely which digraphs are hereditarily hard, i.e., are such that the H -colouring problem is NP-hard for any digraph H ′ containing H as a subdigraph. Expand

Polynomial graph-colorings

- Computer Science, Mathematics
- Discret. Appl. Math.
- 1992

A new technique is introduced for proving that the H -coloring problem is polynomial time decidable for some fixed graphs H . Expand

The Complexity of 3-Colouring H-Colourable Graphs

- Mathematics, Computer Science
- 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
- 2019

A novel combination of the universal-algebraic approach to promise constraint satisfaction, that was recently developed by Barto, Bulín and the authors, with some ideas from algebraic topology is relied on. Expand

Generalized H-coloring and H-covering of Trees

- Computer Science, Mathematics
- Nord. J. Comput.
- 2002

The complexity of H(2p, q)-COLORING is shown to be directly related to these open graph covering problems, and to answer some of them by resolving the complexity ofH(p,q)-COLORing for all acyclic graphs H and all values of p and q. Expand

On the complexity of colouring by superdigraphs of bipartite graphs

- Computer Science, Mathematics
- Discret. Math.
- 1992

The study of the H-colouring problem, that is, the decision problem ‘Is there an H -colouring of a given digraph G ?’, is continued and it is established that this problem is NP-complete whenever H contains a symmetric odd cycle. Expand

Polynomial Graph-Colorings

- Mathematics, Computer Science
- STACS
- 1989

A new technique is introduced for proving that the H-coloring problem is polynomial time decidable for some fixed graphs H, among others, if H is a semipath (a “path” with edges directed in either direction), which has not been known before. Expand

Problems and conjectures on parameterized H-coloring

- Mathematics
- 2002

Recall that given two directed or undirected graphs G = (V (G), E(G)) and G = (V (G), E(G)) an homomorphism of G into G is a map ha θ : V (G) → V (G) with the property that {v,w} ∈ E(G) ⇒ {θ(v),… Expand

#### References

SHOWING 1-10 OF 23 REFERENCES

On the Complexity of the General Coloring Problem

- Mathematics, Computer Science
- Inf. Control.
- 1981

The complexity of the general coloring problem, i.e., of deciding for a given graph G whether some graph H is an interpretation of G, is investigated and it is shown that for many very simple undirected graphs G this question is NP -complete. Expand

The Complexity of Near-Optimal Graph Coloring

- Mathematics, Computer Science
- J. ACM
- 1976

It is proved that even coming close to khgr;(G) with a fast algorithm is hard, and it is shown that if for some constant r < 2 and constant d there exists a polynomial-time algorithm A which guarantees A(G). Expand

On unavoidable digraphs in orientations of graphs

- Mathematics, Computer Science
- J. Graph Theory
- 1987

It is proved that among all G for which G D, the minimum chromatic number is equal to the minimum k for which Kk hom(D) is the set of homomorphs of D, and necessary and sufficient conditions are given for a directed graph to have a homomorphism into a given transitive tournament, directed path, or directed cycle. Expand

NP-completeness of a family of graph-colouring problems

- Computer Science, Mathematics
- Discret. Appl. Math.
- 1983

Each of these problems is shown to be NP-complete by constructing a polynomial transformation from 3-satisfiability to (2 r +1, r )-colourability, valid for each value of r. Expand

On multiplicative graphs and the product conjecture

- Mathematics, Computer Science
- Comb.
- 1988

It is proved that all odd undirected cycles and all prime-power directed cycles have the property of not admitting a homomorphism into G, and this property is derived for a wide class of 3-chromatic graphs studied by Gerards. Expand

On Minimal Graphs

- Mathematics, Computer Science
- Theor. Comput. Sci.
- 1982

It is shown that in a minimal graph G with m vertices, none of them adjacent to all other Vertices, cliques have less than 12m vertices and this bound cannot be improved. Expand

Homomorphisms of 3-chromatic graphs

- Computer Science, Mathematics
- Discret. Math.
- 1985

The principal result (Theorem 2) provides necessary conditions for the existence of a homomorphism onto a prescribed target and it is shown that iterated cartesian products of the Petersen graph form an infinite family of vertex transitive graphs no one of which is the homomorphic image of any other. Expand

An Application of Graph Coloring to Printed Circuit Testing (Working Paper)

- Computer Science, Mathematics
- FOCS 1975
- 1975

Under certain assumptions on the possible types of short circuits, the structure of line-of-sight graphs is analyzed and it is shown that a well known and efficient algorithm can be used to color them with a small number of colors. Expand

Colorings and interpretations: a connection between graphs and grammar forms

- Mathematics, Computer Science
- Discret. Appl. Math.
- 1981

The paper investigates hierarchies of families of graphs obtained by this mechanism, both in the directed and undirected case. Expand

Representations of Graphs by Means of Products and Their Complexity

- Mathematics, Computer Science
- MFCS
- 1981

I. A graph G is a pair (V,E) where V is a finite set and E is either a set of ordered pairs from V (i.e. E ~V × V) or a set of unordered pairs from V (i.e. E ~ [V3 2 ) . In the former case G is… Expand