Ramsey-type � \chi -bounds for � \chi -bounded graph classes

Tung H. Nguyen, Sang-il Oum · 2026

Read Ramsey-type � \chi -bounds for � \chi -bounded graph classes by Tung H. Nguyen, Sang-il Oum (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-08848.txt.

Description

Tung Nguyen and Sang-il Oum bound the hues a graph needs when it bars set patterns. A graph class is chi bounded when its hue count is tied to its top clique size. They prove one clean case first. Graphs that bar any fixed path and the four loop need just a line rate of hues. Then they ask the broad form. The pair is a forest and a full multi part graph.

Two broad cases say yes. One pairs broom shaped forests with any full multi part graph. One pairs any forest with a full two part graph. The proofs join many past line and square rate results. A new, sharp proof of a fresh tree find claim is in the work too.

Catalog record

CREATORTung H. Nguyen, Sang-il Oum
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE73 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.08848

Browse the full library · About the Tower of Babel