Some mader-perfect graph classes

DOI10.1016/J.AMC.2023.127968MaRDI QIDQ6160574zbMATH OpenFDO

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

Publication date 26 June 2023

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2210.06247

zbMATH Keywords

dichromatic numberdigraphstrongly connectedsubdivision

Mathematics Subject Classification ID

Graph theory (05Cxx)

Abstract: The dichromatic number of $D$, denoted by $overrightarrowchi(D)$, is the smallest integer $k$ such that $D$ admits an acyclic $k$-coloring. We use $made{r}_{overrightarrowchi}(F)$ to denote the smallest integer $k$ such that if $overrightarrowchi(D)gek$, then $D$ contains a subdivision of $F$. A digraph $F$ is called Mader-perfect if for every subdigraph $F^{\prime }$ of $F$, ${mmader}_{overrightarrowchi}(F^{\prime })=|V(F^{\prime })|$. 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'{o} [Dichromatic number and forced subdivisions, {it J. Comb. Theory, Ser. B} {�f 153} (2022) 1--30]. We also show that if $K$ is a proper subdigraph of $overleftrightarrow{C}_4$ except for the digraph obtained from $overleftrightarrow{C}_4$ by deleting an arbitrary arc, then $K$ is Mader-perfect.

Recommendations

• Dichromatic number and forced subdivisions
• Subdivisions in digraphs of large out-degree or large dichromatic number
• scientific article; zbMATH DE number 1444491
• scientific article; zbMATH DE number 3918396
• Subdivisions in dicritical digraphs with large order or digirth

Cites work

• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• Dichromatic number and forced subdivisions
• Hajos' graph-coloring conjecture: Variations and counterexamples
• In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen
• Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
• Subdivisions in digraphs of large out-degree or large dichromatic number
• Topological cliques in graphs II
• Vertices of small degree in critically n-connected digraphs

Cited in

(1)

• scientific article; zbMATH DE number 4031747 (Why is no real title available?)

This page was built for publication: Some mader-perfect graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6160574)