Acyclic subgraphs of tournaments with high chromatic number

DOI10.1112/blms.12446zbMath1467.05073arXiv1912.07722OpenAlexW3120703991MaRDI QIDQ4999677

Matthew Kwan, Jacob Fox, Benjamin Sudakov

Publication date: 2 July 2021

Published in: Bulletin of the London Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

oriented graphs\(k\)-chromatic graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (2)

Combinatorial anti-concentration inequalities, with applications ⋮ Every orientation of a 4-chromatic graph has a non-bipartite acyclic subgraph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Acyclic subgraphs with high chromatic number
• Interlacing eigenvalues and graphs
• Oriented trees in digraphs
• Large incidence-free sets in geometries
• A proof of Sumner's universal tournament conjecture for large tournaments
• A Ramsey-Type Theorem for Orderings of a Graph
• Nombre chromatique et plus longs chemins d'un graphe
• Zur algebraischen Begründung der Graphentheorie. I
• Ramsey-type theorems with forbidden subgraphs

This page was built for publication: Acyclic subgraphs of tournaments with high chromatic number