Algorithm for graph homomorphisms ★★

Author(s): Fomin; Heggernes; Kratsch

\begin{question} % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. 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$? \end{question}

Keywords: algorithm; Exponential-time algorithm; homomorphism

Hedetniemi's Conjecture ★★★

Author(s): Hedetniemi

\begin{conjecture} If $G,H$ are simple finite graphs, then $\chi(G \times H) = \min \{ \chi(G), \chi(H) \}$. \end{conjecture}

Here $G \times H$ is the \Def[tensor product]{tensor product of graphs} (also called the direct or categorical product) of $G$ and $H$.

Keywords: categorical product; coloring; homomorphism; tensor product

Weak pentagon problem ★★

Author(s): Samal

\begin{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. \end{conjecture}

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

Mapping planar graphs to odd cycles ★★★

Author(s): Jaeger

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

Keywords: girth; homomorphism; planar graph

Pentagon problem ★★★

Author(s): Nesetril

\begin{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 \Def[homomorphism]{graph_homomorphism} $G \to C_5$? \end{question}

Keywords: cubic; homomorphism

A homomorphism problem for flows ★★

Author(s): DeVos

\begin{conjecture} Let $M,M'$ be abelian groups and let $B \subseteq M$ and $B' \subseteq M'$ satisfy $B=-B$ and $B' = -B'$. If there is a \Def[homomorphism]{graph homomorphism} from $Cayley(M,B)$ to $Cayley(M',B')$, then every graph with a B-flow has a B'-flow. \end{conjecture}

Keywords: homomorphism; nowhere-zero flow; tension

Syndicate content