Poussinův graf - Poussin graph

Poussinův graf
Poussinův graf planar.svg
Vrcholy15
Hrany39
Poloměr3
Průměr3
Obvod3
Automorfismy2 (Z/2Z)
Chromatické číslo4
Chromatický index6
VlastnostiHamiltonian
Rovinný
Tabulka grafů a parametrů
Spletený Kempe řetězy v Poussinově grafu. Sousedství mezi oblastmi této mapy tvoří Poussinův graf, částečně čtyřbarevný s vnější oblastí nezbarvenou. Modro-žluté a modrozelené řetězy Kempe (žluté a zelené čáry) spojují sousedy vnějšího regionu, takže Kempe vyměnil barvy v levém červeno-žlutém řetězci a v pravém červeno-zeleném řetězci (červené čáry), což umožňuje vnější region být červený. Vzhledem k tomu, že se modrozelené a modrozelené řetězce kříží, způsobila by tato barevná výměna červenou a zelenou oblast v horní části červené a vytvořilo by neplatné zabarvení.

V teorii grafů je Poussinův graf je rovinný graf s 15 vrcholy a 39 hranami. Je pojmenován po Charles Jean de la Vallée-Poussin.

Dějiny

V roce 1879 Alfred Kempe zveřejnil doklad o čtyřbarevná věta, jeden z velkých dohadů v teorie grafů.[1]Zatímco věta je pravdivá, Kempeho důkaz je nesprávný. Percy John Heawood to ilustroval v roce 1890[2]s protikladem a de la Vallée-Poussin dospěl ke stejnému závěru v roce 1896 s Poussinův graf.[3]

Kempeho (nesprávný) důkaz je založen na střídavé řetězy a jak se tyto řetězce osvědčily v teorie grafů matematici se i nadále zajímají o tyto protipříklady. Více bylo nalezeno později: zaprvé Errera graf v roce 1921,[4][5]pak Kittellův graf v roce 1935, s 23 vrcholy,[6]a nakonec dva minimální protiklady ( Soiferův graf v roce 1997 a Fritschův graf v roce 1998, oba řádu 9).[7][8][9]

Reference

  1. ^ Kempe, A. B. "O geografickém problému čtyř barev". Amer. J. Math. 2, 193–200, 1879.
  2. ^ P. J. Heawood, „Věta o barevné mapě“, Quart. J. Pure Appl. Matematika. 24 (1890), 332–338.
  3. ^ R. A. Wilson, Graphs, colorings and the four-color theorem, Oxford University Press, Oxford, 2002. PAN1888337 Zbl  1007.05002.
  4. ^ Errera, A. "Du coloriage des cartes et de quelques questions d'analysis situs." Ph.D. teze. 1921.
  5. ^ Peter Heinig. Důkaz, že Errera Graph je úzká Kempe-Impasse. 2007.
  6. ^ Kittell, I. "Skupina operací na částečně zbarvené mapě." Býk. Amer. Matematika. Soc. 41, 407–413, 1935.
  7. ^ A. Soifer, „Mapování barev ve viktoriánském věku: problémy a historie“, Matematické soutěže 10 (1997), 20–31.
  8. ^ R. Fritsch a G. Fritsch, The Four-Color Theorem, Springer, New York, 1998. PAN1633950.
  9. ^ Gethner, E. a Springer, W. M. II. «Jak falešný je Kempeho důkaz čtyřbarevné věty? »Kongr. Číslo. 164, 159–175, 2003.

externí odkazy