Cover Image

Coloring tournaments with few colors: Algorithms and complexity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Klingelhoefer, Felix, Newman, Alantha
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Hardness and Approximation for Coloring Digraphs
by: Chalermsook, Parinya, et al.
Published: (2026)

Improved linearly ordered colorings of hypergraphs via SDP rounding
by: Louis, Anand, et al.
Published: (2024)

Understanding the Cluster LP for Correlation Clustering
by: Cao, Nairen, et al.
Published: (2024)

Deterministic Edge Coloring with few Colors in CONGEST
by: Blikstad, Joakim, et al.
Published: (2026)

Revisiting Directed Disjoint Paths on tournaments (and relatives)
by: Gomes, Guilherme C. M., et al.
Published: (2025)

Solving the Correlation Cluster LP in Sublinear Time
by: Cao, Nairen, et al.
Published: (2025)

Static to Dynamic Correlation Clustering
by: Cao, Nairen, et al.
Published: (2025)

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
by: Bansal, Nikhil, et al.
Published: (2026)

A characterization of one-sided error testable graph properties in bounded degeneracy graphs
by: Lachish, Oded, et al.
Published: (2026)

Arboricity-Dependent Algorithms for Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
by: Assadi, Sepehr, et al.
Published: (2026)

Faster Vizing and Near-Vizing Edge Coloring Algorithms
by: Assadi, Sepehr
Published: (2024)

On the FirstFit Algorithm for Online Unit-Interval Coloring
by: Krekelberg, Bob, et al.
Published: (2025)

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring
by: Ferber, Asaf, et al.
Published: (2025)

Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture
by: Arndt, Stephen, et al.
Published: (2026)

A Near-Real-Time Reduction-Based Algorithm for Coloring Massive Graphs
by: Zhu, Chenghao, et al.
Published: (2025)

Engineering Hypergraph $b$-Matching Algorithms
by: Großmann, Ernestine, et al.
Published: (2024)

Edge-coloring sparse graphs with $Δ$ colors in quasilinear time
by: Kowalik, Lukasz
Published: (2024)

Pointwise Lipschitz Continuous Graph Algorithms
by: Liu, Quanquan C., et al.
Published: (2024)

Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette Sparsification
by: Assadi, Sepehr, et al.
Published: (2025)

Engineering Weighted Connectivity Augmentation Algorithms
by: Faraj, Marcelo Fonseca, et al.
Published: (2024)

QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes
by: Bonnet, Édouard, et al.
Published: (2026)

Above-Guarantee Algorithm for Properly Colored Spanning Trees
by: Bai, Yuhang, et al.
Published: (2026)

Differentially private graph coloring
by: Xie, Michael, et al.
Published: (2026)

A Tight ($3/2 + \varepsilon$)-Approximation Algorithm for Demand Strip Packing
by: Eberle, Franziska, et al.
Published: (2024)

Coloring Reconfiguration under Color Swapping
by: Fuchs, Janosch, et al.
Published: (2025)

KD-Club: An Efficient Exact Algorithm with New Coloring-based Upper Bound for the Maximum k-Defective Clique Problem
by: Jin, Mingming, et al.
Published: (2023)

Finding $b$-colorings Using Feedback Edges
by: Balabán, Jakub
Published: (2025)

Coloring 3-Colorable Graphs with Low Threshold Rank
by: Hsieh, Jun-Ting
Published: (2025)

A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time
by: Dhawan, Abhishek
Published: (2024)

Comparative genomics with succinct colored de Bruijn graphs
by: Ramos, Lucas P., et al.
Published: (2024)

Parallel Derandomization for Coloring
by: Coy, Sam, et al.
Published: (2023)

Kernelization for $H$-Coloring
by: Berkman, Yael, et al.
Published: (2025)

Dynamic O(arboricity) coloring in polylogarithmic worst-case time
by: Ghaffari, Mohsen, et al.
Published: (2024)

Dynamic Edge Coloring of Forests
by: Kaplan, Haim, et al.
Published: (2026)

Pattern Discovery in Colored Strings
by: Lipták, Zsuzsanna, et al.
Published: (2020)

Colorful Priority $k$-Supplier
by: Chekuri, Chandra, et al.
Published: (2024)

Improved Streaming Edge Coloring
by: Chechik, Shiri, et al.
Published: (2025)

FPT Constant Approximation Algorithms for Colorful Sum of Radii
by: Liu, Shuilian, et al.
Published: (2025)