Acyclic subgraphs with high chromatic number

DOI10.1016/j.ejc.2018.07.016zbMath1400.05088arXiv1811.05734OpenAlexW2888222923WikidataQ129349024 ScholiaQ129349024MaRDI QIDQ1621059

Raphael Yuster, Safwat Nassar

Publication date: 15 November 2018

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

3-chromatic acyclic subgraph4-chromatic graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items (3)

Every orientation of a 4-chromatic graph has a non-bipartite acyclic subgraph ⋮ All Feedback Arc Sets of a Random Turán Tournament Have $\lfloor {n}/{k}\rfloor-{k}+1$ Disjoint ${k}$-Cliques (and This Is Tight) ⋮ Acyclic subgraphs of tournaments with high chromatic number

Cites Work

• Unnamed Item
• Unnamed Item
• Oriented trees in digraphs
• On Sets of Acquaintances and Strangers at any Party
• Nombre chromatique et plus longs chemins d'un graphe
• Zur algebraischen Begründung der Graphentheorie. I
• The chromatic number of random graphs
• Totally odd \(K_4\)-subdivisions in 4-chromatic graphs

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