Coloring tournaments with few colors: algorithms and complexity

DOI10.1137/23m1602127MaRDI QIDQ6654122

Alantha Newman, Felix Klingelhoefer

Publication date: 18 December 2024

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

graph coloringtournamentsdicoloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ramsey-type theorems
• On the existence of two non-neighboring subgraphs in a graph
• A still better performance guarantee for approximate graph coloring
• Zero knowledge and the chromatic number
• The 3 and 4-dichromatic tournaments of minimum order
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• The dichromatic number of a digraph
• 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
• Tournaments and colouring
• Coloring tournaments: from local to global
• The hardness of 3-uniform hypergraph coloring
• The removal lemma for tournaments
• Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs
• The Erdös-Hajnal Conjecture-A Survey
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Coloring 3-Colorable Graphs with Less than n ^1/5 Colors
• A Min-Max Theorem on Tournaments
• Conditional Hardness for Approximate Coloring
• On the power of unique 2-prover 1-round games
• Improving the performance guarantee for approximate graph coloring
• Approximate graph coloring by semidefinite programming
• New approximation algorithms for graph coloring
• Coloring bipartite hypergraphs
• On the Hardness of 4-Coloring a 3-Colorable Graph
• 2-Approximating Feedback Vertex Set in Tournaments
• Algebraic approach to promise constraint satisfaction
• Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs
• Coloring dense digraphs
• On the hardness of approximating the chromatic number
• Ramsey-type theorems with forbidden subgraphs
• The smallest 5-chromatic tournament
• Pure pairs. X. Tournaments and the strong Erdős-Hajnal property
• Bounding the chromatic number of dense digraphs by arc neighborhoods

This page was built for publication: Coloring tournaments with few colors: algorithms and complexity