Goldberg – Seymourova domněnka - Goldberg–Seymour conjecture
v teorie grafů the Goldberg – Seymourova domněnka tvrdí, že[1][2]
kde je hranové chromatické číslo z G a
Všimněte si, že výše uvedené množství je dvojnásobek arboricita zG. Někdy se tomu říká hustota zG.[2]
Výše G může být multigraf (může mít smyčky).
Pozadí
Je již známo, že pro bezmocný G (ale může mít rovnoběžné hrany):[2][3]
Kdy rovnost neplatí? To neplatí pro Petersenův graf. Je těžké najít další příklady. V současné době není známo, zda existují rovinné grafy pro které rovnost neplatí.
Tato domněnka je pojmenována po Paul Seymour z Univerzita Princeton, který k němu dorazil nezávisle na Goldbergovi.[3]
Oznámený důkaz
V roce 2019 Chen, Jing a Zang v článku oznámili údajný důkaz.[3] Část jejich důkazu bylo najít vhodné zobecnění Vizingova věta (což říká, že pro jednoduché grafy ) na multigrafy.
Viz také
Reference
- ^ „Problémy v teorii grafů a kombinatorice“. faculty.math.illinois.edu. Citováno 2019-05-05.
- ^ A b C (PDF) https://math.gsu.edu/gchen/files/PPT/Guangming_ALS.pdf. Chybějící nebo prázdný
| název =
(Pomoc) - ^ A b C Zang, Wenan; Jing, Guangming; Chen, Guantao (2019-01-29). „Důkaz hypotézy Goldberg – Seymour o zbarvení hran multigrafů“. arXiv:1901.10316v1. Citovat deník vyžaduje
| deník =
(Pomoc)