Abstract
The dichromatic number of D, denoted by χ→(D), is the smallest integer k such that D admits an acyclic k-coloring. We use maderχ→(F) to denote the smallest integer k such that if χ→(D)≥k, then D contains a subdivision of F. A digraph F is called Mader-perfect if for every subdigraph F′ of F, maderχ→(F′)=|V(F′)|. We extend octi digraphs to a larger class of digraphs and prove that it is Mader-perfect, which generalizes a result of Gishboliner, Steiner and Szabó [Dichromatic number and forced subdivisions, J. Comb. Theory, Ser. B 153 (2022) 1–30]. We also show that if K is a proper subdigraph of C↔4 except for the digraph obtained from C↔4 by deleting an arbitrary arc, then K is Mader-perfect.
| Original language | English |
|---|---|
| Article number | 127968 |
| Journal | Applied Mathematics and Computation |
| Volume | 450 |
| DOIs | |
| State | Published - 1 Aug 2023 |
Keywords
- Dichromatic number
- Digraph
- Strongly connected
- Subdivision
Fingerprint
Dive into the research topics of 'Some mader-perfect graph classes'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver