Erdős – Gyárfás dohad - Erdős–Gyárfás conjecture

Question, Web Fundamentals.svgNevyřešený problém v matematice:
Musí každý kubický graf obsahovat jednoduchý cyklus délky a sílu dvou?
(více nevyřešených úloh z matematiky)
Markströmův graf
Markström-Graph.svg
Markströmův 24-vertexový kubický planární graf bez 4 nebo 8 cyklů, nalezený v počítači při hledání protipříkladů hypotézy Erdős – Gyárfás. Má však cykly s 16 vrcholy.
Vrcholy24
Hrany36
Poloměr5
Průměr6
Obvod3
Automorfismy3
Tabulka grafů a parametrů

v teorie grafů, neprokázané Erdős – Gyárfás dohad, vyrobený v roce 1995 plodným matematikem Paul Erdős a jeho spolupracovník András Gyárfás, uvádí, že každý graf s minimem stupeň 3 obsahuje a jednoduchý cyklus jehož délka je a síla dvou. Erdős nabídl cenu 100 $ za prokázání domněnky, nebo 50 $ za protiklad; je to jeden z mnoha dohady Erdőse.

Pokud je domněnka nepravdivá, měl by protipříklad příklad grafu s minimálním stupněm tři, který nemá sílu dvou cyklů. Je známo z počítačového vyhledávání Gordon Royle a Klas Markström, že jakýkoli protipříklad musí mít alespoň 17 vrcholů a jakýkoli krychlový protiklad musí mít alespoň 30 vrcholů. Markströmova hledání našla čtyři grafy na 24 vrcholech, ve kterých má jediná síla dvou cyklů 16 vrcholů. Jeden z těchto čtyř grafů je rovinný; nyní je však známo, že domněnka Erdős – Gyárfás platí pro speciální případ 3 spojených kubických planárních grafů (Heckman & Krakovski 2013 )

Slabší výsledky týkající se stupně grafu s nevyhnutelnými množinami délek cyklu jsou známy: existuje množina S délek, s |S| = O (n0.99), takže každý graf s průměrným stupněm deset nebo více obsahuje cyklus s jeho délkou v S (Verstraëte 2005 ) a každý graf, jehož průměrný stupeň je v iterovaný logaritmus z n nutně obsahuje cyklus, jehož délka je síla dvou (Sudakov & Verstraëte 2008 ). Je také známo, že domněnka platí pro rovinné grafy bez drápů (Daniel & Shauger 2001 ) a pro grafy, které se vyhnou velkým indukovaným hvězdy a uspokojit další omezení jejich stupňů (Shauger 1998 ).

Reference

  • Daniel, Dale; Shauger, Stephen E. (2001), „Výsledek domněnky Erdős – Gyárfás v rovinných grafech“, Proc. 32. jihovýchodní int. Konf. Kombinatorika, teorie grafů a výpočetní technika, s. 129–139.
  • Heckman, Christopher Carl; Krakovski, Roi (2013), „Erdös-Gyárfásova domněnka pro kubické rovinné grafy“, Electronic Journal of Combinatorics, 20 (2), P7.
  • Markström, Klas (2004), "Extrémní grafy pro některé problémy na cyklech v grafech" (PDF), Congr. Numerantium, 171: 179–192.
  • Shauger, Stephen E. (1998), „Výsledky domněnky Erdős – Gyárfás v K.1,m-bezplatné grafy ", Proc. 29. jihovýchodní int. Konf. Kombinatorika, teorie grafů a výpočetní technika, s. 61–65
  • Sudakov, Benny; Verstraëte, Jacques (2008), „Délka cyklu v řídkých grafech“, Combinatorica, 28 (3): 357–372, arXiv:0707.2117, doi:10.1007 / s00493-008-2300-6.
  • Verstraëte, Jacques (2005), „nevyhnutelné délky cyklu v grafech“, Journal of Graph Theory, 49 (2): 151–167, doi:10.1002 / jgt.20072.

externí odkazy