Erdős-Gyarfaş hypotese

Uløste problemer i matematik : Indeholder en kubisk graf en simpel cyklus af længde en potens af to?

Erdős-Gyarfas-formodningen  er et uløst problem i grafteori

Ordlyd

Enhver graf med hjørnepunkter på mindst 3 indeholder en simpel cyklus af længde svarende til en potens af to.

Historie

Hypotesen blev formuleret i 1995 af de ungarske matematikere Pal Erdős og András Gyarfas.

Computersøgning af Gordon Royleog Klas Markström viste , at ethvert modeksempel skal have minimum 17 hjørner og ethvert kubisk modeksempel skal have minimum 30 knudepunkter. Markströms søgning gav fire grafer med 24 hjørner, der har cyklusser af grad på to med kun 16 hjørner, hvor en af ​​disse grafer er plan .

Et svagere resultat er kendt om graden af ​​en graf, der indeholder længdecyklusser fra et sæt: der er et sæt længder, c , sådan at enhver graf med en gennemsnitlig grad på ti eller mere indeholder en længdecyklus fra [1] . Det er også kendt, at formodningen er sand for plane grafer uden klør [2] og for grafer, der ikke har store stjerner , og som opfylder yderligere begrænsninger for graden af ​​toppunkter [3] .

Noter

  1. ↑ Jacques Verstraëte. Uundgåelige cykluslængder i grafer // Journal of Graph Theory. - 2005. - T. 49 , no. 2 . — S. 151–167 . - doi : 10.1002/jgt.20072 .
  2. ↑ Dale Daniel, Stephen E. Shauger. Proc. 32nd Southeastern Int. Konf. Kombinatorik, grafteori og computing. - 2001. - S. 129-139.
  3. ↑ Stephen E. Shauger. Proc. 29th Southeastern Int. Konf. Kombinatorik, grafteori og computing. - 1998. - S. 61-65.

Litteratur

Links