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

CREATORNadzieja Hodur, Monika Pilśniak, Magdalena Prorok, Ingo Schiermeyer
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-07229

Browse the full library · About the Tower of Babel