Wykres Poussina

Wykres Poussina
Wierzchołki	15
Krawędzie	39
Promień	3
Średnica	3
Obwód	3
Automorfizmy	2 ( Z /2 Z )
Liczba chromatyczna	4
Indeks chromatyczny	6
Nieruchomości	Planar Hamiltona
Tabela wykresów i parametrów

Splątane łańcuchy Kempe na wykresie Poussina. Przylegania pomiędzy regionami tej mapy tworzą wykres Poussina, częściowo czterokolorowy, z obszarem zewnętrznym niepokolorowanym. Niebiesko-żółty i niebiesko-zielony łańcuch Kempe (żółte i zielone linie) łączą sąsiadów regionu zewnętrznego, więc Kempe zamieniłby kolory w lewym czerwono-żółtym łańcuchu i prawym czerwono-zielonym łańcuchu (czerwone linie), umożliwiając regionowi zewnętrznemu być czerwony. Gdy łańcuchy niebiesko-żółty i niebiesko-zielony się krzyżują, ta zamiana kolorów spowodowałaby, że górne obszary żółty i zielony stałyby się czerwone, co spowodowałoby nieprawidłowe zabarwienie.

W teorii grafów graf Poussina jest grafem planarnym mającym 15 wierzchołków i 39 krawędzi. Jej nazwa pochodzi od Charlesa Jeana de la Vallée-Poussina .

Historia

W 1879 roku Alfred Kempe opublikował dowód twierdzenia o czterech kolorach , jednego z najważniejszych założeń teorii grafów . Chociaż twierdzenie jest prawdziwe, dowód Kempe jest błędny. Percy John Heawood zilustrował to w 1890 r. kontrprzykładem, a de la Vallée-Poussin doszedł do tego samego wniosku w 1896 r., przedstawiając wykres Poussina .

(Niepoprawny) dowód Kempe opiera się na naprzemiennych łańcuchach , a ponieważ łańcuchy te okazują się przydatne w teorii grafów, matematycy pozostają zainteresowani takimi kontrprzykładami. Więcej znaleziono później: najpierw graf Errery w 1921 r., następnie graf Kittella w 1935 r. z 23 wierzchołkami i wreszcie dwa minimalne kontrprzykłady (wykres Soifera w 1997 r. i graf Fritscha w 1998 r., oba rzędu 9).

Linki zewnętrzne

• Eric W. Weisstein , Wykres Poussina ( MathWorld )