# homomorphism

## Algorithm for graph homomorphisms ★★

Author(s): Fomin; Heggernes; Kratsch

Question

Is there an algorithm that decides, for input graphs and , whether there exists a homomorphism from to in time for some constant ?

## Hedetniemi's Conjecture ★★★

Author(s): Hedetniemi

Conjecture   If are simple finite graphs, then .

Here is the tensor product (also called the direct or categorical product) of and .

## Weak pentagon problem ★★

Author(s): Samal

Conjecture   If is a cubic graph not containing a triangle, then it is possible to color the edges of by five colors, so that the complement of every color class is a bipartite graph.

## Mapping planar graphs to odd cycles ★★★

Author(s): Jaeger

Conjecture   Every planar graph of girth has a homomorphism to .

Keywords: girth; homomorphism; planar graph

## Pentagon problem ★★★

Author(s): Nesetril

Question   Let be a 3-regular graph that contains no cycle of length shorter than . Is it true that for large enough~ there is a homomorphism ?

Keywords: cubic; homomorphism

## A homomorphism problem for flows ★★

Author(s): DeVos

Conjecture   Let be abelian groups and let and satisfy and . If there is a homomorphism from to , then every graph with a B-flow has a B'-flow.

Keywords: homomorphism; nowhere-zero flow; tension