Coloring tournaments with few colors: algorithms and complexity
From MaRDI portal
Publication:6654122
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)
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
