.png){kind=icon}
.png){kind=icon}
Return
Some mader-perfect graph classes
.png){kind=icon}
OA
AI
DOI：10.1016/j.amc.2023.127968.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The dichromatic number of D , denoted by (chi) over right arrow (D ) , is the smallest integer k such that D admits an acyclic k-coloring. We use mader ((chi) over right arrow) (F ) to denote the smallest integer k such that if (chi) over right arrow (D ) >= k , then D contains a subdivision of F . A digraph F is called Mader-perfect if for every subdigraph F' of F, made ((chi) over right arrow)(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 Szabo [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 obtained from (C) over left right arrow (4) except for the digraph (C) over left right arrow (4) by deleting an arbitrary arc, then K is Mader-perfect. (c) 2023 Published by Elsevier Inc.
Keywords:
Digraph
Dichromatic number
Subdivision
Strongly connected
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.4
Papers:
2.3W
Citations:
3.3W