
Homomorphisms
Cores of Cayley graphs ★★
Author(s): Samal



Keywords: Cayley graph; core
Pentagon problem ★★★
Author(s): Nesetril




Keywords: cubic; homomorphism
Mapping planar graphs to odd cycles ★★★
Author(s): Jaeger


Keywords: girth; homomorphism; planar graph
Weak pentagon problem ★★
Author(s): Samal


Keywords: Clebsch graph; cut-continuous mapping; edge-coloring; homomorphism; pentagon
Algorithm for graph homomorphisms ★★
Author(s): Fomin; Heggernes; Kratsch
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
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
Keywords: choosability; circular colouring; planar graphs
