Albertsonova hypotéza

Nevyřešené úlohy v matematice : Mají úplné grafy nejmenší možný počet průsečíků mezi grafy se stejným chromatickým číslem ?

Albertsonův dohad  je neprokázané spojení mezi číslem průniku a chromatickým číslem grafu . Hypotéza je pojmenována po Michaelu O. Albertsonovi, profesorovi na Smith College , který toto tvrzení formuloval jako hypotézu v roce 2007 [1] . Dohad je jedním z mnoha dohadů v teorii zbarvení grafů [2] . Dohad říká, že mezi všemi grafy vyžadujícími n barev je úplný graf K n mezi grafy s nejmenším počtem průsečíků. Ekvivalentně, jestliže graf může být nakreslen s méně průsečíky než Kn , pak, domněnkou, může být obarven méně než n barvami .

Hypotetický vzorec pro minimální počet křižovatek

Lze přímo ukázat, že graf s omezeným počtem průsečíků má omezený chromatický počet - koncům všech protínajících se hran můžete přiřadit různé barvy a obarvit rovinný graf zbývající po odstranění těchto hran 4 barvami . Albertsonova hypotéza nahrazuje tento kvalitativní vztah mezi počtem průniků a počtem barev přesnějším kvantitativním vztahem. Další domněnka Richarda K. Guye [3] uvádí, že počet průsečíků úplného grafu K n je

Je známo, jak nakreslit kompletní grafy s tímto počtem průsečíků, umístěním vrcholů na dvě soustředné kružnice. Není známo, zda existují výkresy s menším počtem řezů. Posílená formulace Albertsonovy domněnky tedy říká, že jakýkoli n -chromatický graf má průsečíkové číslo ne menší než pravá strana tohoto vzorce [4] . Tato posílená domněnka je pravdivá tehdy a jen tehdy, když jsou pravdivé jak domněnky Guye, tak Albertsonovy domněnky.

Asymptotické hranice

Slabší forma domněnky, kterou dokázal M. Schaefer [4] , uvádí, že každý graf s chromatickým číslem n má průsečíkové číslo Ω( n 4 ), nebo ekvivalentně, že každý graf s průsečíkem k má chromatické číslo O ( k 1/4 ). Alberson , chromatický graf má minimální stupeň ne menší nežnpublikovali důkaz těchto hranic kombinací skutečnosti, že jakýkoli minimální[4]Kratson a Fox nerovností čísel průsečíku , podle které má každý graf c číslo průsečíku ). Pomocí stejných argumentů ukazují, že protipříklad k Albertsonově domněnce s chromatickým číslem n (pokud existuje) musí mít méně než 4n vrcholů.

Zvláštní příležitosti

Albertsonova domněnka je pravdivé tvrzení bez obsahu pro  - má průsečík číslo nula a všechny grafy mají průsečík alespoň nula. Případ Albertsonovy domněnky je ekvivalentní větě o čtyřech barvách , že každý rovinný graf může být obarven čtyřmi nebo méně barvami a jediné grafy, které vyžadují méně průsečíků než graf K 5 , jsou rovinné grafy, podle hypotézy by měly být maximálně než 4-chromatické. Díky podpoře některých skupin autorů je dnes známo, že domněnka platí pro všechny [5] [4] [6] . Pro jakékoli celé číslo Louis a Richter představili rodiny (c+1) -barevně kritických grafů, které neobsahují poddělení celého grafu K (c+1) , ale mají alespoň K (c+1) průsečíků [7] .

Související hypotézy

Existuje také souvislost s Hadwigerovým dohadem , důležitým otevřeným problémem v kombinatorice týkajícím se souvislosti mezi chromatickým číslem a existencí velkých klik jako graf minor [6] . Varianta Hadwigerova dohadu předložená György Hajosem říká , že nějaký n - chromatický graf obsahuje pododdělení Kn . Pokud by domněnka byla pravdivá, pak by z ní vyplývala Albertsonova domněnka, protože počet průsečíků úplného grafu není menší než počet průsečíků dělení. V současnosti jsou však známy protipříklady k Hayoshově domněnce [8] [9] , takže toto spojení neumožňuje Albertsonovu domněnku dokázat.

Poznámky

  1. ↑ Podle Albertsona, Cranstona a Foxe ( Albertson, Cranston, Fox 2009 ) domněnku vznesl Albertson na zvláštním zasedání American Mathematical Society v Chicagu, které se konalo v říjnu 2007.
  2. ↑ Hutchinson, 2009 .
  3. ↑ Chlap, 1972 .
  4. ↑ 1 2 3 4 Albertson, Cranston, Fox, 2009 .
  5. ↑ Oporowski, Zhao, 2009 .
  6. ↑ 1 2 Barát, Toth, 2010 .
  7. ↑ Louis, Richter, 2014 .
  8. ↑ Catlin, 1979 .
  9. ↑ Erdős, Fajtlowicz, 1981 .

Literatura