Гипотеза Гольдберга – Сеймура

В теории графов гипотеза Гольдберга – Сеймура утверждает, что ^{[ 1 ]}^{[ 2 ]}

\operatorname {\chi '} G\leq \max(1+\operatorname {\Delta } G,\,\operatorname {\Gamma } G)

где $\operatorname {\chi '} G$ - краевое хроматическое G и число

\operatorname {\Gamma } G=\max _{H\subset G}{\frac {|E(H)|}{\lfloor {\frac {1}{2}}|V(H)|\rfloor }}.

что указанная выше величина в два раза превышает древесность G Обратите внимание , . называют плотностью G. ее Иногда ^{[ 2 ]}

Выше G может быть мультиграф (может иметь петли ).

Фон

Уже известно, что для без петель G (но может иметь параллельные края): ^{[ 2 ]}^{[ 3 ]}

\operatorname {\chi '} G\geq \max(\operatorname {\Delta } G,\lceil \operatorname {\Gamma } G\rceil ).

Когда равенство не имеет места? Это не справедливо для графа Петерсена . Трудно найти другие примеры. В настоящее время неизвестно, существуют ли планарные графы , для которых не выполняется равенство.

Эта гипотеза названа в честь Марка К. Голдберга из Политехнического института Ренсселера. ^{[ 4 ]} и Пол Сеймур из Принстонского университета , прибывший в него независимо от Голдберга. ^{[ 3 ]}

Объявлено доказательство

В 2019 году о предполагаемом доказательстве в газете. Чэнь, Цзин и Занг объявили ^{[ 3 ]}. Часть их доказательства заключалась в том, чтобы найти подходящее обобщение теоремы Визинга (которая гласит, что для простых графов $\operatorname {\chi '} G\leq 1+\operatorname {\Delta } G$ ) к мультиграфам. В 2023 году Цзин ^{[ 5 ]} объявил о новом доказательстве с помощью алгоритма раскраски ребер за полиномиальное время, позволяющего достичь предполагаемой границы .

См. также

Ссылки

^ «Проблемы теории графов и комбинаторики» . факультет.математика.illinois.edu . Проверено 5 мая 2019 г.
^ Jump up to: ^а ^б ^с Цзин, Гуанмин (2018). «Гипотеза Гольдберга-Сеймура о граничной раскраске мультиграфов» (PDF) . Государственный университет Джорджии.
^ Jump up to: ^а ^б ^с Занг, Вэнань; Цзин, Гуанмин; Чен, Гуантао (29 января 2019 г.). «Доказательство гипотезы Гольдберга – Сеймура о раскрасках ребер мультиграфов». arXiv : 1901.10316v1 [ math.CO ].
^ Гольдберг, Марк (1984). «Раскраска краев мультиграфов: техника перекраски». Журнал теории графов . 8 (1): 123–137. дои : 10.1002/jgt.3190080115 .
^ Цзин, Гуанмин (29 августа 2023 г.). «Реберная раскраска мультиграфов». arXiv : 2308.15588 [ math.CT ].

[1] «Проблемы теории графов и комбинаторики» . факультет.математика.illinois.edu . Проверено 5 мая 2019 г.

[:1-2] Jump up to: ^а ^б ^с Цзин, Гуанмин (2018). «Гипотеза Гольдберга-Сеймура о граничной раскраске мультиграфов» (PDF) . Государственный университет Джорджии.

[:0-3] Jump up to: ^а ^б ^с Занг, Вэнань; Цзин, Гуанмин; Чен, Гуантао (29 января 2019 г.). «Доказательство гипотезы Гольдберга – Сеймура о раскрасках ребер мультиграфов». arXiv : 1901.10316v1 [ math.CO ].

[4] Гольдберг, Марк (1984). «Раскраска краев мультиграфов: техника перекраски». Журнал теории графов . 8 (1): 123–137. дои : 10.1002/jgt.3190080115 .

[:4-5] Цзин, Гуанмин (29 августа 2023 г.). «Реберная раскраска мультиграфов». arXiv : 2308.15588 [ math.CT ].

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]