On 3-colorability of (claw, diamond)-free graphs

Abstract

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 belong to some well-defined class of non $3$-colorable graphs. Moreover, we prove that there are only finitely many non $3$-colorable $N_{1,2,k}$-free graphs for any $k\ge 2$, but there exist infinitely many non $3$-colorable $N_{i,j,k}$-free graphs for any $2\le i\le j\le k.$