Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-10T05:36:28.844Z Has data issue: false hasContentIssue false
  • English
  • Français

One More Probabilistic Reformulation of the Four Colour Conjecture

Published online by Cambridge University Press:  24 August 2010

Yu. MATIYASEVICH
Yu. MATIYASEVICH*
Affiliation:
St. Petersburg Department of Steklov Institute of Mathematics, 27 Fontanka, St. Petersburg 191023, Russia (e-mail: yumat@pdmi.ras.ru)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The paper presents yet another way to reformulate the Four Colour Conjecture as a statement concerning conditional probabilities of certain events involving planar graphs.

References

[1]Appel, K. and Haken, W. (1977) Every planar map is four colorable I: Discharging. Illinois J. Math. 21 429–490.Google Scholar
[2]Appel, K., Haken, W. and Koch, J. (1977) Every planar map is four colorable II: Reducibility. Illinois J. Math. 21 491–567.Google Scholar
[3]Appel, K. and Haken, W. (1989) Every Planar Map is Four Colorable, Vol. 98 of Contemporary Mathematics, AMS, Providence, RI.Google Scholar
[4]Gonthier, G. (2008) Formal proof: The four-color theorem. Notices Amer. Math. Soc. 55 1382–1393.Google Scholar
[5]Goodall, A. J. (2004) Graph polynomials and the discrete Fourier transform. PhD thesis, University of Oxford.Google Scholar
[6]Goodall, A. J. (2006) Some new evaluations of the Tutte polynomial. J. Combin. Theory Ser. B 96 207–224.Google Scholar
[7]Goodall, A. J. (2008) Parity, Eulerian subgraphs and the Tutte polynomial. J. Combin. Theory Ser. B 98 599–628.Google Scholar
[8]Kauffman, L. H. (1990) Map coloring and the vector cross product. J. Combin. Theory Ser. B 48 145–154.Google Scholar
[9]Kung, J. P. S. (2008) Coboundaries, flows, and Tutte polynomials of matrices. Ann. Combin. 12 183–194.Google Scholar
[10]Matiyasevich, Yu. V. (2003) A probabilistic equivalent to the four-color conjecture (in Russian). Teor. Veroyatnost. i Primenen. 48 411–416. Translation in Theory Probab. Appl. 48 (2004) 368–372.Google Scholar
[11]Matiyasevich, Yu. (2004) Some probabilistic restatements of the four color conjecture. J. Graph Theory 46 167–179.CrossRefGoogle Scholar
[12]Penrose, R. (1971) Applications of negative dimensional tensors. In Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press, pp. 221–244.Google Scholar
[13]Robertson, N., Sanders, D., Seymour, P. and Thomas, R. (1997) The four-colour theorem. J. Combin. Theory Ser. B 70 2–44.Google Scholar
[14]Scheim, D. E. (1974) The number of edge 3-colorings of a planar cubic graph as a permanent. Discrete Math. 8 377–382.Google Scholar