Back to Search
Start Over
Some mader-perfect graph classes.
- Source :
-
Applied Mathematics & Computation . Aug2023, Vol. 450, pN.PAG-N.PAG. 1p. - Publication Year :
- 2023
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *INTEGERS
*STEINER systems
*RAMSEY numbers
Subjects
Details
- Language :
- English
- ISSN :
- 00963003
- Volume :
- 450
- Database :
- Academic Search Index
- Journal :
- Applied Mathematics & Computation
- Publication Type :
- Academic Journal
- Accession number :
- 163165112
- Full Text :
- https://doi.org/10.1016/j.amc.2023.127968