Kelmanova – Seymourova domněnka - Kelmans–Seymour conjecture

K.5 dělení 12-vrcholů korunový graf

v teorie grafů, Kelmans – Seymourova domněnka uvádí, že každý 5-vrchol připojený graf, který není rovinný obsahuje a pododdělení 5-vrcholu kompletní graf K.5. Je pojmenován pro Paul Seymour a Alexander Kelmans, který nezávisle popsal domněnku; Seymour v roce 1977 a Kelmans v roce 1979.[1][2] Důkaz byl oznámen, ale dosud nebyl zveřejněn.[1][3]

Formulace

Graf je připojen k 5 vrcholům, když není pět vrcholů, jejichž odstranění zanechává odpojený graf. Celý graf je graf s hranou mezi každých pět vrcholů a dělení úplného grafu to upravuje nahrazením některých jeho hran delšími cestami. Takže graf G obsahuje pododdělení K.5 pokud je možné vybrat pět vrcholů G, a sada deseti cest spojujících těchto pět vrcholů v párech, aniž by některá z cest sdílela vrcholy nebo hrany navzájem.

V každém kreslení grafu na euklidovské rovině se musí alespoň dvě z deseti cest protínat, takže graf G který obsahuje a K.5 dělení nemůže být a rovinný graf. V opačném směru by Kuratowského věta, graf, který není rovinný, nutně obsahuje dělení obou K.5 nebo kompletní bipartitní graf K.3,3Kelmanova – Seymourova domněnka tuto teorém zpřesňuje tím, že poskytuje podmínku, za níž je možné pouze jedno z těchto dvou pododdělení, dělení K.5, lze zaručeně existovat. Uvádí, že pokud je nerovinný graf spojen s 5 vrcholy, obsahuje další členění K.5.

Související výsledky

Související výsledek, Wagnerova věta, uvádí, že každý neplanární graf připojený ke 4 vrcholům obsahuje kopii K.5 jako graf minor. Jedním ze způsobů přepracování tohoto výsledku je, že v těchto grafech je vždy možné provést posloupnost kontrakce hran operace tak, aby výsledný graf obsahoval a K.5 pododdělení. Kelmanova – Seymourova domněnka uvádí, že s vyšším řádem konektivity nejsou tyto kontrakce nutné.

Dřívější domněnka Gabriel Andrew Dirac (1964), prokázaný v roce 2001 Wolfgangem Maderem, uvádí, že každý n-vertexový graf s minimem 3n − 5 edge obsahuje dělení K.5. Protože rovinné grafy mají nanejvýš 3n − 6 okraje, grafy minimálně 3n − 5 hrany musí být nerovinné. Nemusí však být spojeny 5 a grafy s 5 spoji mohou mít jen málo 2.5n hrany.[4][5][6]

Nárokovaný důkaz

V roce 2016 tvrdil Xingxing Yu z. Důkaz domněnky Kelmans – Seymour Gruzínský technologický institut a jeho Ph.D. studenti Dawei He a Yan Wang.[3]V časopise Journal of Combinatorial Theory Series B se objevila sekvence čtyř článků dokazujících tuto domněnku.[7][8][9][10]

Viz také

Reference

  1. ^ A b Condie, Bill (30. května 2016), „Matematické tajemství vyřešeno po 40 letech“, Kosmos.
  2. ^ Všimněte si však, že Thomassen (1997) datuje Seymourovu formulaci domněnky do roku 1984.
  3. ^ A b On, Dawei; Wang, Yan; Yu, Xingxing (16. listopadu 2015), Kelmanova – Seymourova domněnka I: zvláštní separace, arXiv:1511.05020; ——; et al. (24. února 2016), Kelmanova – Seymourova domněnka II: 2 vrcholy , arXiv:1602.07557; ——; et al. (19. září 2016), Kelmanova – Seymourova domněnka III: 3 vrcholy , arXiv:1609.05747; ——; et al. (21. prosince 2016), Kelmanova – Seymourova domněnka IV: Důkaz, arXiv:1612.07189
  4. ^ Dirac, G. A. (1964), „Věty o homomorfismu pro grafy“, Mathematische Annalen, 153: 69–80, doi:10.1007 / BF01361708, PAN  0160203
  5. ^ Thomassen, Carsten (1997), „Diracova domněnka o -dělení ", Diskrétní matematika, 165/166: 607–608, doi:10.1016 / S0012-365X (96) 00206-3, PAN  1439305
  6. ^ Mader, W. (1998), " okraje vynutí rozdělení na ", Combinatorica, 18 (4): 569–595, doi:10,1007 / s004930050041, PAN  1722261
  7. ^ On, Dawei; Wang, Yan; Yu, Xingxing (11. 12. 2019). „Domněnka Kelmans-Seymour I: Zvláštní separace“. Journal of Combinatorial Theory, Series B. arXiv:1511.05020. doi:10.1016 / j.jctb.2019.11.008. ISSN  0095-8956.
  8. ^ On, Dawei; Wang, Yan; Yu, Xingxing (11. 12. 2019). „Kelmans-Seymourova domněnka II: 2-vrcholy v K4−“. Journal of Combinatorial Theory, Series B. arXiv:1602.07557. doi:10.1016 / j.jctb.2019.11.007. ISSN  0095-8956.
  9. ^ On, Dawei; Wang, Yan; Yu, Xingxing (09.12.2019). „Kelmans-Seymourova domněnka III: 3 vrcholy v K4−“. Journal of Combinatorial Theory, Series B. arXiv:1609.05747. doi:10.1016 / j.jctb.2019.11.006. ISSN  0095-8956.
  10. ^ On, Dawei; Wang, Yan; Yu, Xingxing (2019-12-19). „Domněnka Kelmans-Seymour IV: Důkaz“. Journal of Combinatorial Theory, Series B. arXiv:1612.07189. doi:10.1016 / j.jctb.2019.12.002. ISSN  0095-8956.