{"id":"arxiv/2602.07229","url":"https://arxiv.org/abs/2602.07229","tags":["math.CO"],"score":0,"title":"On 3-colorability of (claw, diamond)-free graphs","domain":"math.CO","source":"arxiv","authors":["Nadzieja Hodur","Monika Pilśniak","Magdalena Prorok","Ingo Schiermeyer"],"reviews":0,"subject":"math.CO","summary":"The $3$-colorability problem is a well-known NP-complete problem and it remains NP-complete for $(claw, diamond, K_4)$-free graphs. Recently, $3$-colorability has been also considered for $(claw, N_{1,1,1})$-free graphs. Here, a generalised net $N_{i, j, k}$ is the graph obtained by identifying each vertex of a triangle with an endvertex of one of three vetex-disjont paths of lengths $i, j, k$. We study the class of $(claw, diamond, N_{i, j, k})$-free graphs for $(i, j, k) \\in \\{(1, 1, 3),$ $ (1, 2, 2), $ $(2, 2, 2) \\}$. We show that these graphs are $3$-colorable or contain a $K_4$ or…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-06","reactions":{}}