Complete directed minors and chromatic number

dc.contributor.authorMészáros, Tamás
dc.contributor.authorSteiner, Raphael
dc.date.accessioned2022-12-21T10:13:52Z
dc.date.available2022-12-21T10:13:52Z
dc.date.issued2022-06-07
dc.date.updated2022-11-22T18:14:06Z
dc.description.abstractThe dichromatic number χ→(D) of a digraph D is the smallest k for which it admits a k‐coloring where every color class induces an acyclic subgraph. Inspired by Hadwiger's conjecture for undirected graphs, several groups of authors have recently studied the containment of complete directed minors in digraphs with a given dichromatic number. In this note we exhibit a relation of these problems to Hadwiger's conjecture. Exploiting this relation, we show that every directed graph excluding the complete digraph K↔t of order t as a strong minor or as a butterfly minor is O(t(log log t)6)‐colorable. This answers a question by Axenovich, Girão, Snyder, and Weber, who proved an upper bound of t4t for the same problem. A further consequence of our results is that every digraph of dichromatic number 22n contains a subdivision of every n‐vertex subcubic digraph, which makes progress on a set of problems raised by Aboulker, Cohen, Havet, Lochet, Moura, and Thomassé.en
dc.description.sponsorshipDFG, 390685689, EXC 2046: MATH+: Berlin Mathematics Research Center
dc.description.sponsorshipDFG, 385256563, GRK 2434: Facetten der Komplexität
dc.description.sponsorshipTU Berlin, Open-Access-Mittel – 2022
dc.identifier.eissn1097-0118
dc.identifier.issn0364-9024
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/17872
dc.identifier.urihttps://doi.org/10.14279/depositonce-16661
dc.language.isoen
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subject.ddc510 Mathematikde
dc.subject.otherchromatic number
dc.subject.otherdirected graphs
dc.subject.othergraph minors
dc.subject.otherHadwiger's conjecture
dc.titleComplete directed minors and chromatic numberen
dc.typeArticle
dc.type.versionpublishedVersion
dcterms.bibliographicCitation.doi10.1002/jgt.22844
dcterms.bibliographicCitation.issue4
dcterms.bibliographicCitation.journaltitleJournal of Graph Theoryen
dcterms.bibliographicCitation.originalpublishernameWiley
dcterms.bibliographicCitation.originalpublisherplaceNew York, NY
dcterms.bibliographicCitation.pageend632
dcterms.bibliographicCitation.pagestart623
dcterms.bibliographicCitation.volume101
dcterms.rightsHolder.referenceCreative-Commons-Lizenz
tub.accessrights.dnbfree
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik::FG Diskrete Mathematik
tub.publisher.universityorinstitutionTechnische Universität Berlin

Files

Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
JGT_JGT22844.pdf
Size:
406.62 KB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
4.86 KB
Format:
Item-specific license agreed upon to submission
Description:

Collections