Ancillary-file links:
Ancillary files (details):
References & Citations
Mathematics > Combinatorics
Title: On 3-colourability of $(bull, H)$-free graphs
(Submitted on 18 Apr 2024)
Abstract: The $3$-colourability problem is a well-known NP-complete problem and it remains NP-complete for $bull$-free graphs, where $bull$ is the graph consisting of $K_3$ with two pendant edges attached to two of its vertices. In this paper we study $3$-colourability of $(bull,H)$-free graphs for several graphs $H$. We show that these graphs are $3$-colourable or contain an induced odd wheel $W_{2p+1}$ for some $p\geq 2$ or a spindle graph $M_{3p+1}$ for some $p\geq 1$. Moreover, for all our results we can provide certifying algorithms that run in polynomial time.
Submission history
From: Nadzieja Hodur Msc [view email][v1] Thu, 18 Apr 2024 21:31:09 GMT (851kb,AD)
Link back to: arXiv, form interface, contact.