The Count of Poussin is a planar graph with 15 vertices and 39 edges. It is named after Charles Jean de la Valle-Poussin .
| Count of Poussin | |
|---|---|
 | |
| Top | 15 |
| Riber | 39 |
| Radius | 3 |
| Diameter | 3 |
| Girth | 3 |
| Automorphisms | ( Z / 2 Z ) |
| Chromatic number | four |
| Chromatic Index | 6 |
| The properties | hamilton planar |
History
In 1879, published a proof of the four-color theorem , one of the great hypotheses in graph theory [1] . Although the theorem itself is true, Kempe's proof is erroneous. demonstrated this in 1890 [2] with a counterexample, while de La Vallee-Poussin came to the same conclusion in 1896 with the Earl of Poussin [3] .
Kempe’s (false) proof is based on , and since this chain-based proof has proven useful in graph theory , mathematicians continue to be interested in such counterexamples. Other counterexamples were found later, this is Herrera’s count in 1921 [4] [5] , Kittell’s count in 2335 with 23 vertices [6], and finally, two minimal counterexamples (Count Soyfer in 1997 and in 1998, both order 9) [7] [8] [9] .
Other properties
The clique width of the graph is 7 [10] .
Notes
- ↑ Kempe, 1879 , p. 193-200.
- ↑ Heawood, 1890 , p. 332–338.
- ↑ Wilson, 2002 .
- ↑ Errera, 1921 .
- ↑ Heinig, 2007 .
- ↑ Kittell, 1935 , p. 407-413.
- ↑ Soifer, 1997 , p. 20–31.
- ↑ Fritsch, Fritsch, 1998 .
- ↑ Gethner, Springer, 2003 , p. 159-175.
- ↑ HEULE, SZEIDER, 2015 , p. 00:19, Table III.
Literature
- Kempe AB On the Geographical Problem of Four-Colors // Amer. J. Math .. - 1879. - Issue. 2 .
- Heawood PJ Map color theorem // Quart. J. Pure Appl. Math .. - 1890. - Issue. 24 .
- Wilson RA Graphs, colorings and the four-color theorem. - Oxford: Oxford University Press, 2002.
- Errera A. Du coloriage des cartes et de quelques questions d'analysis situs .. - 1921. - (Ph.D. thesis).
- Peter Heinig. Proof that the Errera Graph is a narrow Kempe-Impasse . - 2007.
- Kittell I. A Group of Operations on a Partially Colored Map // Bull. Amer. Math. Soc. - 1935. - T. 41 , no. 6 . - DOI : 10.1090 / S0002-9904-1935-06104-X .
- Soifer A. Map coloring in the victorian age: problems and history // Mathematics Competitions. - 1997. - Vol. 10 .
- Fritsch R., Fritsch G. The Four-Color Theorem. - New York: Springer, 1998.
- Gethner E., Springer WM II. How False Is Kempe's Proof of the Four-Color Theorem? // Congr. Numer .. - 2003. - Vol. 164 .
- MARIJN JH HEULE, STEFAN SZEIDER. A SAT approach to clique-width. // ACM Transactions on Computational Logic. - 2015. - Issue. 0.0 (January 2015) . - DOI : 10.1145 / 0000000.000000 .
Links
- Eric W. Weisstein , Poussin Graph ( MathWorld )