On 3 3 -colorability of ( c l a w , d i a m o n d ) (claw,diamond) -free graphs
Nadzieja Hodur, Monika Pilśniak, Magdalena Prorok, Ingo Schiermeyer · 2026
Read On 3 3 -colorability of ( c l a w , d i a m o n d ) (claw,diamond) -free graphs by Nadzieja Hodur, Monika Pilśniak, Magdalena Prorok, Ingo Schiermeyer (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-2602-07229.txt.
Description
Deciding whether a graph can be colored with three colors is famously hard in general, but restrictions on forbidden subgraphs can tame it. Nadzieja Hodur and three co-authors study graphs free of claws, diamonds, and generalized nets of three specific shapes.
They show such graphs are either 3-colorable, contain a complete graph on four vertices, or belong to a well-defined class of exceptions. They also prove only finitely many non-3-colorable cases exist for one family of nets, while infinitely many exist for another. Graph theorists get a sharp classification that maps exactly where the hard cases live and where they end.
Catalog record
| CREATOR | Nadzieja Hodur, Monika Pilśniak, Magdalena Prorok, Ingo Schiermeyer |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 34 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-07229