Homomorphisms

Cores of Cayley graphs ★★

Author(s): Samal

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

Keywords: Cayley graph; core

Posted by Robert Samal
updated February 29th, 2012

3 comments

Graph Theory » Coloring » Homomorphisms

Pentagon problem ★★★

Author(s): Nesetril

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

Keywords: cubic; homomorphism

Posted by Robert Samal
updated March 24th, 2007

add new comment

Graph Theory » Coloring » Homomorphisms

Mapping planar graphs to odd cycles ★★★

Author(s): Jaeger

Conjecture Every planar graph of girth $\ge 4k$ has a homomorphism to $C_{2k+1}$ .

Keywords: girth; homomorphism; planar graph

Posted by mdevos
updated June 24th, 2007

add new comment

Graph Theory » Coloring » Homomorphisms

Weak pentagon problem ★★

Author(s): Samal

Conjecture If $G$ is a cubic graph not containing a triangle, then it is possible to color the edges of $G$ 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

Posted by Robert Samal
updated July 13th, 2007

add new comment

Graph Theory » Coloring » Homomorphisms

Algorithm for graph homomorphisms ★★

Author(s): Fomin; Heggernes; Kratsch

Question

Is there an algorithm that decides, for input graphs $G$ and $H$ , whether there exists a homomorphism from $G$ to $H$ in time $O(c^{|V(G)|+|V(H)|})$ for some constant $c$ ?

Keywords: algorithm; Exponential-time algorithm; homomorphism

Posted by jfoniok
updated July 8th, 2010

add new comment

Graph Theory » Coloring » Homomorphisms

Circular choosability of planar graphs ★

Author(s): Mohar

Let $G = (V, E)$ be a graph. If $p$ and $q$ are two integers, a $(p,q)$ -colouring of $G$ is a function $c$ from $V$ to $\{0,\dots,p-1\}$ such that $q \le |c(u)-c(v)| \le p-q$ for each edge $uv\in E$ . Given a list assignment $L$ of $G$ , i.e.~a mapping that assigns to every vertex $v$ a set of non-negative integers, an $L$ -colouring of $G$ is a mapping $c : V \to N$ such that $c(v)\in L(v)$ for every $v\in V$ . A list assignment $L$ is a $t$ - $(p,q)$ -list-assignment if $L(v) \subseteq \{0,\dots,p-1\}$ and $|L(v)| \ge tq$ for each vertex $v \in V$ . Given such a list assignment $L$ , the graph G is $(p,q)$ - $L$ -colourable if there exists a $(p,q)$ - $L$ -colouring $c$ , i.e. $c$ is both a $(p,q)$ -colouring and an $L$ -colouring. For any real number $t \ge 1$ , the graph $G$ is $t$ - $(p,q)$ -choosable if it is $(p,q)$ - $L$ -colourable for every $t$ - $(p,q)$ -list-assignment $L$ . Last, $G$ is circularly $t$ -choosable if it is $t$ - $(p,q)$ -choosable for any $p$ , $q$ . The circular choosability (or circular list chromatic number or circular choice number) of G is $cch(G) := \inf\{t \ge 1 : G \text{ is circularly $t$-choosable}\}.$