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
| CREATOR | Tung H. Nguyen, Sang-il Oum |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 73 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.08848