zbMATH — the first resource for mathematics

One more probabilistic reformulation of the four colour conjecture. (English) Zbl 1261.05095
The author here gives another equivalent reformulation of the four colour conjecture (now a theorem!) for planar graphs: see for example his papers [Theory Probab. Appl. 48, No. 2, 368–372 (2003); translation from Teor. Veroyatn. Primen. 48, No. 2, 411–416 (2003; Zbl 1051.05044)] and [J. Graph Theory 46, No. 3, 167–179 (2004; Zbl 1053.05050)]. (In earlier work, he had given an equivalent formulation in terms of number theory: see e.g., R. Thomas [Notices Am. Math. Soc. 45, No. 7, 848–859 (1998; Zbl 0908.05040)]).
The reformulation here is in terms of the statement that, in every two-connected planar cubic graph \(G\) with \(3n\) edges, the event that two randomly selected orientations of the line graph are ‘congruent \(\mod 3\)’ - that is, they have the out-degrees in the two orientations congruent \(\mod 3\). Call this event \(B_{G}\). The result is that the four-color theorem is equivalent to the statement that \(B_{G}\) is not independent of the event \(A_{G}\), that two randomly selected orientations of the line graph have the same parity (in a suitable technical sense). More precisely, we get (with \(\chi_{G}(4)\) denoting the number of proper 4-colourings of \(G\)) \[ \mathbb{P}(B_{G}| A_{G})-\mathbb{P}(B_{G})=\frac{\chi_{G}(4)}{4}\left(\frac{27}{4096}\right)^{n}. \]
Some other reformulations are presented as well. The result seems not to be new: it appears to be equivalent to Theorem 5.4.4. in Andrew Goodall’s D.Phil thesis at Oxford in 2004 (unpublished, but see http://kam.mff.cuni.cz/~andrew/AJGthesis.pdf). However the proof here is non-trivially shorter.
05C80 Random graphs (graph-theoretic aspects)
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI
[1] DOI: 10.1016/j.jctb.2007.09.006 · Zbl 1162.05019 · doi:10.1016/j.jctb.2007.09.006
[2] DOI: 10.1007/s00026-008-0346-1 · Zbl 1169.05013 · doi:10.1007/s00026-008-0346-1
[3] DOI: 10.1016/0095-8956(90)90114-F · Zbl 0638.05025 · doi:10.1016/0095-8956(90)90114-F
[4] DOI: 10.1016/j.jctb.2005.07.007 · Zbl 1090.05033 · doi:10.1016/j.jctb.2005.07.007
[5] Gonthier, Notices Amer. Math. Soc. 55 pp 1382– (2008)
[6] Appel, Every Planar Map is Four Colorable (1989) · Zbl 0681.05027 · doi:10.1090/conm/098
[7] Matiyasevich, Teor. Veroyatnost. i Primenen. 48 pp 411– (2003) · doi:10.4213/tvp295
[8] DOI: 10.1016/0012-365X(74)90157-5 · Zbl 0281.05103 · doi:10.1016/0012-365X(74)90157-5
[9] Appel, Illinois J. Math. 21 pp 429– (1977)
[10] DOI: 10.1006/jctb.1997.1750 · Zbl 0883.05056 · doi:10.1006/jctb.1997.1750
[11] Penrose, Combinatorial Mathematics and its Applications pp 221– (1971)
[12] DOI: 10.1002/jgt.10178 · Zbl 1053.05050 · doi:10.1002/jgt.10178
[13] Appel, Illinois J. Math. 21 pp 491– (1977)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.