0
$\begingroup$

Planar graphs with a Hamiltonian loop connecting all faces do not necessarily have a Hamiltonian on their edges, which would make a 3 edge coloring and thus a 4 face coloring easy. However they have a lot of great structure. If you split the graph along the face Hamiltonian using it like an equator,the edges in the northern or southern hemisphere form trees. Thus the problem of coloring Hamiltonian planar graphs with n faces reduces to finding a mutual edge 3 coloring of any two n trees.

Regarding the Hamiltonian graphs as compositions of trees makes them easily counted, and gives a relation between graphs by relating their trees.

Between trees of the same size: Any tree of size n may converted into another of size n by iterated diamond switches, DS, of internal branches. I have proven any n-tree can be converted into any other n-tree in less than 2n DS. Nicely, if 2 trees are within n DS they have a mutual coloring.

Between trees of different sizes: Larger and smaller Hamiltonian graphs can be made by adding or subtracting branches that cross the equator, preserving the Hamiltonian loop. So inductive proofs are encouraged.

Also any tree of n roots has exactly 2^(n-3) colorings , which can be arranged on a hypercube, so you could prove all Hamiltonian graphs with n faces are colorable by proving any two color-hypercubes of n-trees intersect.

Hamiltonian graphs are a good restricted simpler group of graphs to try to prove colorable, interesting in their own right. They are even more important if their colorability implies the colorability of all planar graphs. Is it so?

$\endgroup$
5
  • 3
    $\begingroup$ There is notable lack of clarity (and capitalization). $\endgroup$ Aug 15, 2010 at 4:31
  • $\begingroup$ thank you for reading my query. Please advise me on what is unclear.? Isnt the question "does the colorability of planar Hamiltonian graphs imply all planar graphs are colorable" clear? Shall I capitalize all beginings of sentences? $\endgroup$ Aug 15, 2010 at 16:00
  • $\begingroup$ I don't see what most of the first paragraph has to do with the question. $\endgroup$
    – HJRW
    Aug 15, 2010 at 17:50
  • $\begingroup$ Also, by 'colorable', do you mean '4-colorable'? $\endgroup$
    – HJRW
    Aug 15, 2010 at 17:51
  • $\begingroup$ I suppose I should have asked two questions 1)Are all planar Hamiltonian graphs 4 colorable ? 2)If so, then are does this imply all planar graphs are 4 colorable? Then the first paragraph is about reducing Hamiltonian planar graphs to compositions of trees which reduces the first question to the mutual edge colorability of any two trees. (This presupposes you know Taits theorem that 4 coloring faces is equivalent to 3 coloring the edges.) The second question I have not made any real headway on, so I have no discussion , only the question. $\endgroup$ Aug 16, 2010 at 3:47

1 Answer 1

6
$\begingroup$

If $G$ is a graph all of whose faces are triangles, and $G'$ is its dual, then recall that $G$ is $4$-vertex-colorable if and only if $G'$ is $3$-edge-colorable. It is unclear whether you are asking about the situation of $G$ or of $G'$ having a Hamiltonian cycle. As far as I know (but I am not a graph theorist), there is no relation between these two conditions.

Whitney's theorem says that, modulo some minor hypotheses, $G$ has a Hamiltonian cycle. Specifically:

Whitney's Theorem: Let $G$ be a planar graph all of whose faces are triangles. Suppose that $G$ contains no loops, no multiple edges, and no $3$-cycles which are not faces. Then $G$ has a Hamiltonian cycle.

$4$-colorability for graphs that meet the hypotheses of Whitney's theorem easily implies $4$-colorability of all planar graphs.

If $G'$ has a Hamiltonian cycle, then $G'$ is trivially $3$-edge-colorable. Graphs of the form $G'$ tend to be Hamiltonian. This is true both rigorously -- Hamiltonian graphs have density approaching $1$ among cubic graphs with $n$ labeled vertices (see Robinson and Wormwald) and as a statement about common experience -- the smallest counter-examples have about 36 vertices and are not obvious. MathSciNet recommends this survey for more on Hamiltonianicity of cubic graphs.

$\endgroup$
2
  • $\begingroup$ what do you mean by no 3-cycles which are not faces? Aren't all 3-cycles in a planar graph faces? $\endgroup$
    – Turbo
    May 1, 2016 at 2:48
  • 2
    $\begingroup$ Consider the bipyramid: Take two tetrahedra and glue them face to face. The result is a planar graph with five vertices, six triangular faces and, also a $3$-cycle which is not a face. $\endgroup$ May 1, 2016 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.