ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Conjecture 1. For any g \geq 0, we have χw (Sg ) = 4. In [2] it is proved that for any surface X and ǫ > 0, there exists w > 0 such that every G ֒\to X with ew(G) > w satisfies (5) χc (G) \leq χloc (G) + ǫ. In view of (4) this implies that we may replace “χc (G)” with “χloc (G)” in the definition (3). If, further, X is orientable, then we may replace “χc (G)” with “\phic (G∗ )” in definition (3). Thus Conjecture 1 is equivalent to the assertion that for any g and ǫ > 0, wide enough embedded graphs G ֒\to Sg satisfy \phic (G) < 4 + ǫ. By standard “lifting arguments” (such as in [7]) it suffices to verify this assertion for cubic graphs G. Grünbaum [4] has proposed something much stronger than Conjecture 1. Conjecture 2. For any G ֒\to Sg such that ew(G∗ ) \geq 3 we have \phic (G) = 4. Equivalently, Grünbaum asserts that every cubic graph G ֒\to Sg with fw(G) \geq 3 is three edge colourable. (Here, the facewidth fw(G) is the least number of points in which a noncontractible curve in Sg meets G. For cubic embedded graphs we have fw(G) = ew(G∗ ) .) The following weak form of Grünbaum’s conjecture would suffice to prove Con- jecture 1. Conjecture 3. For any g there exists w such that every cubic graph G ֒\to Sg with ew(G) \geq w is 3-edge colourable. Conjecture 3 may be informally stated, “snarks on Sg have bounded facewidth”. On the negative side, it seems to be difficult to find a nontrivial class of graphs for which any of these conjectures can be proven. Even worse, I have not been able to demonstrate χw (Sg ) < 5 for some g > 0. On the positive side, wide embedded graphs G ֒\to Sg for which χc > 4 seem to be difficult to construct. Steve Fisk [3] proposed an a class of graphs (called Fisk graphs) with this property. He showed that if every face of G ֒\to Sg is a triangle, and there are exactly two vertices of odd degree, and these two vertices are adjacent, then χ(G) \geq 5. Fisk graphs of arbitrary edgewidth exist on every Sg 6= S0 . If Conjecture 3 holds, then by (5), χc (G) is only very slightly greater than 4 for any wide Fisk graph G ֒\to Sg . To date, the best I have been able to show [unpublished] is that χloc (G) < 5 for a very special subclass of Fisk triangulations on the torus.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.