Back to Search Start Over

Some mader-perfect graph classes.

Authors :
Lang, Rongling
Lei, Hui
Li, Siyan
Lian, Xiaopan
Wang, Susu
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]

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