Importance: Medium ✭✭
Author(s): DeVos, Matt
Recomm. for undergrads: no
Prize: bottle of wine (DeVos)
Posted by: mdevos
on: June 22nd, 2007

\begin{conjecture} There exists a fixed constant $c$ (probably $c=4$ suffices) so that every embedded (loopless) graph with edge-width $\ge c$ has a 5-local-tension. \end{conjecture}

The \emph{edge-width} of an embedded graph is the length of the shortest non-contractible cycle.

\begin{definition} Let $G$ be a directed graph, let $\Gamma$ be an abelian group, and let $\phi : E(G) \rightarrow \Gamma$. Define the \emph{height} of a walk $W$ to be the sum of $\phi$ on the forward edges of $W$ minus the sum of $\phi$ on the backward edges of $W$ (edges are counted according to multiplicity). We call $\phi$ a \emph{tension} if the height of every closed walk is zero, and if $G$ is an embedded graph, we call $\phi$ a \emph{local-tension} if the height of every closed walk which forms a contractible curve is zero. If in addition, $\Gamma = {\mathbb Z}$ and $0 < \phi(e) < k$ for some $k \in {\mathbb Z}$, we say that $\phi$ is a $k$-\emph{tension} or a $k$-\emph{local-tension}. If we reverse an edge $e$ and replace $\phi(e)$ by $-\phi(e)$, this preserves the properties of tension or local-tension. Accordingly, we say that an undirected graph (embedded graph) $G$ has a $k$-tension ($k$-local-tension) if some and thus every orientation of it admits such a map. \end{definition}

\begin{proposition} A graph has a $k$-tension if and only if it is $k$-colorable. \end{proposition}

\begin{proof} To see the "if" direction, let $f : V(G) \rightarrow \{0,\ldots,k-1\}$ be a coloring, orient the edges of $G$ arbitrarily, and defining $\phi : E(G) \rightarrow {\mathbb Z}$ by the rule $\phi(uv) = f(v) - f(u)$. It is straightforward to check that $\phi$ is a $k$-tension. For the "only if" direction, let $\phi : E(G) \rightarrow {\mathbb Z}$ be a $k$-tension. Now choose a point $u \in V(G)$ and define the map $f : V(G) \rightarrow {\mathbb Z}_k$ by the rule that $f(v)$ is the height of some (and thus every) walk from $u$ to $v$ modulo $k$. Again, it is straightforward to check that this defines a proper $k$-coloring. \end{proof}

For graphs on orientable surfaces, local-tensions are dual to flows. More precisely, if $G$ and $G^*$ are dual graphs embedded in an orientable surface, then $G$ has a $k$-local-tension if and only if $G^*$ has a nowhere-zero $k$-flow. On non-orientable surfaces, there is a duality between $k$-local-tensions in $G$ and nowhere-zero $k$-flows in a bidirected $G^*$. Based on this duality we have a couple of conjectures. The first follows from \OPrefnum[Tutte's 5-flow conjecture]{126}, the second from \OPrefnum[Bouchet's 6-flow conjecture]{131}.

\begin{conjecture}[Tutte] Every loopless graph embedded in an orientable surface has a 5-local-tension. \end{conjecture}

\begin{conjecture}[Bouchet] Every loopless graph embedded in any surface has a 6-local-tension. \end{conjecture}

So although, graphs on surfaces may have high chromatic number, thanks to some partial results toward the above conjectures, we know that they always have small local-tensions. For orientable surfaces, there is a famous \OPrefnum[Conjecture of Grunbaum]{177} which is equivalent to the following.

\begin{conjecture}[Grunbaum] If $G$ is a simple loopless graph embedded in an orientable surface with edge-width $\ge 3$, then $G$ has a 4-local-tension. \end{conjecture}

On non-orientable surfaces, it is known that there are graphs of arbitrarily high edge-width which do not admit 4-local-tensions (see [DGMVZ]). However, it remains open whether sufficiently high edge-width forces the existence of a 5-local-tension. Indeed, as suggested by the conjecture at the start of this page, it may be that edge-width at least 4 is enough. Edge-width 3 does not suffice since the embedding of $K_6$ in the projective plane does not admit a 5-local-tension.


*[DGMVZ] M. DeVos, L. Goddyn, B. Mohar, D. Vertigan, and X. Zhu, Coloring-flow duality of embedded graphs. Trans. Amer. Math. Soc. 357 (2005), no. 10 \MRhref{2159697}

* indicates original appearance(s) of problem.


Comments are limited to a maximum of 1000 characters.