5-local-tensions

 Importance: Medium ✭✭
 Author(s): DeVos, Matt
 Subject: Graph Theory » Topological Graph Theory » » Coloring
 Keywords: coloring surface tension
 Prize: bottle of wine (DeVos)
 Posted by: mdevos on: June 22nd, 2007
Conjecture   There exists a fixed constant (probably suffices) so that every embedded (loopless) graph with edge-width has a 5-local-tension.

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

Definition   Let be a directed graph, let be an abelian group, and let . Define the height of a walk to be the sum of on the forward edges of minus the sum of on the backward edges of (edges are counted according to multiplicity). We call a tension if the height of every closed walk is zero, and if is an embedded graph, we call a local-tension if the height of every closed walk which forms a contractible curve is zero. If in addition, and for some , we say that is a -tension or a -local-tension. If we reverse an edge and replace by , this preserves the properties of tension or local-tension. Accordingly, we say that an undirected graph (embedded graph) has a -tension ( -local-tension) if some and thus every orientation of it admits such a map.
Proposition   A graph has a -tension if and only if it is -colorable.
Proof   To see the "if" direction, let be a coloring, orient the edges of arbitrarily, and defining by the rule . It is straightforward to check that is a -tension. For the "only if" direction, let be a -tension. Now choose a point and define the map by the rule that is the height of some (and thus every) walk from to modulo . Again, it is straightforward to check that this defines a proper -coloring.

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

Conjecture  (Tutte)   Every loopless graph embedded in an orientable surface has a 5-local-tension.
Conjecture  (Bouchet)   Every loopless graph embedded in any surface has a 6-local-tension.

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 Conjecture of Grunbaum which is equivalent to the following.

Conjecture  (Grunbaum)   If is a simple loopless graph embedded in an orientable surface with edge-width , then has a 4-local-tension.

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 in the projective plane does not admit a 5-local-tension.

Bibliography

*[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 MathSciNet

* indicates original appearance(s) of problem.