Extension of Gyárfás-Sumner conjecture to digraphs

DOI10.37236/9906zbMATH Open1470.05049arXiv2009.13319OpenAlexW3163954842WikidataQ113693632 ScholiaQ113693632MaRDI QIDQ2030749

Author name not available (Why is that?)

Publication date: 7 June 2021

Published in: (Search for Journal in Brave)

Abstract: The dichromatic number of a digraph $D$ is the minimum number of colors needed to color its vertices in such a way that each color class induces an acyclic digraph. As it generalizes the notion of the chromatic number of graphs, it has been a recent center of study. In this work we look at possible extensions of Gy'arf'as-Sumner conjecture. More precisely, we propose as a conjecture a simple characterization of finite sets $mathcalF$ of digraphs such that every oriented graph with sufficiently large dichromatic number must contain a member of $mathcalF$ as an induce subdigraph. Among notable results, we prove that oriented triangle-free graphs without a directed path of length $3$ are $2$-colorable. If condition of "triangle-free" is replaced with "$K_4$-free", then we have an upper bound of $414$. We also show that an orientation of complete multipartite graph with no directed triangle is 2-colorable. To prove these results we introduce the notion of emph{nice sets} that might be of independent interest.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Extension of Gyárfás-Sumner conjecture to digraphs

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