Erdős-Gyarfaş hypotes

Olösta problem i matematik : Innehåller en kubikgraf en enkel cykel av längd en potens av två?

Erdős-Gyarfas gissningar  är ett olöst problem inom grafteorin

Formulering

Varje graf med hörn av grad på minst 3 innehåller en enkel längdcykel lika med en potens av två.

Historik

Hypotesen formulerades 1995 av de ungerska matematikerna Pal Erdős och András Gyarfas.

Datorsökning av Gordon Royleoch Klas Markström visade att varje motexempel måste ha minst 17 hörn och vilket kubiskt motexempel som helst måste ha minst 30 hörn. Markströms sökning gav fyra grafer med 24 hörn som har gradcykler på två med endast 16 hörn, varav en av dessa är plan .

Ett svagare resultat är känt om graden av en graf som innehåller längdcykler från någon uppsättning: det finns en uppsättning längder, c , så att varje graf med en medelgrad på tio eller mer innehåller en cykel med längd från [1] . Det är också känt att antagandet är sant för plana grafer utan klor [2] och för grafer som inte har stora stjärnor och som uppfyller ytterligare begränsningar för graden av hörn [3] .

Anteckningar

  1. ↑ Jacques Verstraëte. Oundvikliga cykellängder i grafer // Journal of Graph Theory. - 2005. - T. 49 , nr. 2 . — S. 151–167 . - doi : 10.1002/jgt.20072 .
  2. ↑ Dale Daniel, Stephen E. Shauger. Proc. 32nd Southeastern Int. Konf. Kombinatorik, grafteori och beräkning. - 2001. - S. 129-139.
  3. ↑ Stephen E. Shagger. Proc. 29th Southeastern Int. Konf. Kombinatorik, grafteori och beräkning. - 1998. - S. 61-65.

Litteratur

Länkar