[Tim Chow sent me mail: From: "Timothy Chow" Date: Mon, 17 Feb 1997 15:01:22 -0500 (EST) To: rusin@math.niu.edu Subject: Planar map coloring The contents are below; the reader will have to sort the attributions, but none of them are from Rusin -- djr] ============================================================================== From dsanders@math.ohio-state.edu Thu Dec 5 12:59:16 1996 Return-Path: Date: Thu, 5 Dec 1996 12:57:23 -0500 (EST) From: Daniel Sanders To: william@math.princeton.edu, tycchow@math.mit.edu Subject: sci.math posting Content-Length: 2569 I don't use sci.math, but a friend showed me your postings. You have restated a problem and reproved a theorem in an area that is dear to me. As Ore and Plummer [OP] did in 1969, let me define an angular coloring of a plane graph to be a coloring of its faces such that two faces which meet at at least a point must have different colors. Let Delta be the maximum degree of the graph considered, i.e. the maximum number of faces which meet at any point of the map. If Delta=3, this is precisely the Four Color Problem. You stated the problem for Delta=4. An equivalent version of this was first stated by Ringel [R] (famous for solving Heawood's map color theorem) in 1965. Problems which are equivalent (in a sense) are the following: vertex-face coloring: coloring the vertices and faces of a planar graph so that two faces which share an edge have different colors, to adjacent vertices have different colors, and a vertex has a different color from its incident faces. coloring the vertices of 1-planar graphs, i.e. graphs which embed in the plane so that each edge crosses at most one other edge. Ringel gave an upper bound of 7 colors, as you did for these three problems, and a lower bound of 6 colors, as you did as well. The theorem that 6 colors suffice for each of these three problems was proved by Borodin [Ba] in 1984. An improved proof in English has recently appeared in [Bb]. His proof is along the lines of, but not as difficult as, the known proofs of the Four Color Theorem (he needs no computer). The best known upper bound for the angular coloring problem (or called the cyclic coloring problem in the dual) was given by Borodin, Zhao, and myself [BSZ] and is (9/5)Delta. The best known lower bound is (3/2)Delta. I am very happy that you find these problems interesting. This problem remains open for all Delta >= 5. Now prove that the lower bound of (3/2)Delta is tight. ---dps References [Ba] O.V.Borodin, Solution of Ringel's problems on vertex-face coloring of plane graphs and coloring of 1-planar graphs (in Russian), Met. Diskret. Anal. 41 (1984) 12-26. [Bb] O.V.Borodin, A new proof of the 6-color theorem, J. Graph Theory 19 (1995) 507-521. [BSZ] O.V.Borodin, D.P.Sanders, and Y.Zhao, Cyclic colorings and their generalizations, to appear. [OP] O.Ore and M.D.Plummer, Cyclic coloration of planar graphs, Recent Progress in Combinatorics; Academic Press, New York (1969) 287-293. [R] G.Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Sem. Univ. Hamburg 29 (1965) 107-117. ==============================================================================