# homomorphism

## Sidorenko's Conjecture ★★★

Author(s): Sidorenko

**Conjecture**For any bipartite graph and graph , the number of homomorphisms from to is at least .

Keywords: density problems; extremal combinatorics; 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 ?

Keywords: algorithm; Exponential-time algorithm; homomorphism

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

Keywords: categorical product; coloring; homomorphism; tensor product

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

Keywords: Clebsch graph; cut-continuous mapping; edge-coloring; homomorphism; pentagon

## 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