On $k$-colorability of $(bull, H)$-free graphs

Nadzieja Hodur; Monika Pilśniak; Magdalena Prorok; Ingo Schiermeyer

paper

On $k$ -colorability of $(b u l l, H)$ -free graphs

arXiv:2509.01698

Abstract

The $3$ -colorability problem is a well-known NP-complete problem and it remains NP-complete for $b u l l$ -free graphs, where a $b u l l$ is the graph consisting of a $K_{3}$ with two pendant edges attached to two of its vertices. In this paper, for $k \geq 3$ , we characterize all $k$ -colorable $(b u l l, c l a w)$ -free graphs containing an induced cycle of length at least $6$ . Moreover, we present the full characterization of all non $4$ -colorable connected $(b u l l, c l a w)$ -free graphs and $(b u l l, c hai r, C_{5})$ -free graphs, and all non $5$ -colorable connected $(b u l l, c l a w, C_{5})$ -free graphs.

On k-colorability of (bull,H)-free graphs

Abstract

On $k$ -colorability of $(b u l l, H)$ -free graphs