Some mader-perfect graph classes

Rongling Lang, Hui Lei, Siyan Li, Xiaopan Lian and Susu Wang

Applied Mathematics and Computation, 2023, vol. 450, issue C

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. B153 (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.

Keywords: Digraph; Dichromatic number; Subdivision; Strongly connected (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300323001376
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:450:y:2023:i:c:s0096300323001376

DOI: 10.1016/j.amc.2023.127968

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().