Skip to main navigation Skip to search Skip to main content

Some mader-perfect graph classes

  • Rongling Lang
  • , Hui Lei*
  • , Siyan Li
  • , Xiaopan Lian
  • , Susu Wang
  • *Corresponding author for this work
  • Nankai University

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Article number127968
JournalApplied Mathematics and Computation
Volume450
DOIs
StatePublished - 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