Szczegóły publikacji
Opis bibliograficzny
On k-colorability of ($bull,H$)-free graphs / Nadzieja HODUR, Monika PILŚNIAK, Magdalena PROROK, Ingo SCHIERMEYER // Discrete Mathematics ; ISSN 0012-365X . — 2026 — vol. 349 iss. 7 art. no. 115054, s. 1–8. — Bibliogr. s. 8, Abstr. — Publikacja dostępna online od: 2026-02-13. — I. Schiermeyer - dod. afiliacja: TU Bergakademie Freiberg, Freiberg, Germany
Autorzy (4)
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 166088 |
|---|---|
| Data dodania do BaDAP | 2026-03-10 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.disc.2026.115054 |
| Rok publikacji | 2026 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Mathematics |
Abstract
The 3-colorability problem is a well-known NP-complete problem and it remains NP-complete for bull-free graphs, where a bull is the graph consisting of a K3 with two pendant edges attached to two of its vertices. In this paper, for k >_ 3, we characterize all k-colorable (bull, claw)-free graphs containing an induced cycle of length at least 6. Moreover, we present the full characterization of all non 4-colorable connected (bull, claw)-free graphs and (bull, chair, C5)-free graphs, and all non 5-colorable connected (bull, claw, C5)-free graphs.
