# Homomorphisms

## Cores of Cayley graphs ★★

Author(s): Samal

Conjecture   Let be an abelian group. Is the core of a Cayley graph (on some power of ) a Cayley graph (on some power of )?

Keywords: Cayley graph; core

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

## Mapping planar graphs to odd cycles ★★★

Author(s): Jaeger

Conjecture   Every planar graph of girth has a homomorphism to .

Keywords: girth; homomorphism; planar graph

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

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

## Circular choosability of planar graphs ★

Author(s): Mohar

Let be a graph. If and are two integers, a -colouring of is a function from to such that for each edge . Given a list assignment of , i.e.~a mapping that assigns to every vertex a set of non-negative integers, an -colouring of is a mapping such that for every . A list assignment is a --list-assignment if and for each vertex . Given such a list assignment , the graph G is --colourable if there exists a --colouring , i.e. is both a -colouring and an -colouring. For any real number , the graph is --choosable if it is --colourable for every --list-assignment . Last, is circularly -choosable if it is --choosable for any , . The circular choosability (or circular list chromatic number or circular choice number) of G is

Problem   What is the best upper bound on circular choosability for planar graphs?

Keywords: choosability; circular colouring; planar graphs