Cover Image

Coloring 3-Colorable Graphs with Low Threshold Rank

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Hsieh, Jun-Ting
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Online Edge Coloring: Sharp Thresholds
by: Blikstad, Joakim, et al.
Published: (2025)

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

Solving Random Planted CSPs below the $n^{k/2}$ Threshold
by: Basu, Arpon, et al.
Published: (2025)

Faster MAX-CUT on Bounded Threshold Rank Graphs
by: Anderson, Prashanti, et al.
Published: (2025)

Exponential Time Approximation for Coloring 3-Colorable Graphs
by: Guruswami, Venkatesan, et al.
Published: (2024)

Connectivity Labeling in Faulty Colored Graphs
by: Petruschka, Asaf, et al.
Published: (2024)

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
by: Ghoshal, Suprovat, et al.
Published: (2026)

Online Graph Coloring for $k$-Colorable Graphs
by: Kawarabayashi, Ken-ichi, et al.
Published: (2025)

Dynamic Graph Coloring: Sequential, Parallel, and Distributed
by: Ghaffari, Mohsen, et al.
Published: (2025)

Online Coloring for Graphs of Large Odd Girth
by: Yoneda, Hirotaka, et al.
Published: (2026)

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

Coloring Graphs with Few Colors in the Streaming Model
by: Assadi, Sepehr, et al.
Published: (2025)

Minimum Sum Coloring with Bundles in Trees and Bipartite Graphs
by: Ito, Takehiro, et al.
Published: (2025)

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

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

Density-Dependent Graph Orientation and Coloring in Scalable MPC
by: Ghaffari, Mohsen, et al.
Published: (2026)

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

Sampling Proper Colorings on Line Graphs Using $(1+o(1))Δ$ Colors
by: Wang, Yulin, et al.
Published: (2023)

Improving the Threshold for Finding Rank-1 Matrices in a Subspace
by: Dastidar, Jeshu, et al.
Published: (2025)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
by: Guruswami, Venkatesan, et al.
Published: (2024)

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

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

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

Sparsifying Cayley Graphs on Every Group
by: Hsieh, Jun-Ting, et al.
Published: (2025)

Sampling Colorings with Fixed Color Class Sizes
by: Kuchukova, Aiya, et al.
Published: (2026)

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

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

Hardness and Approximation for Coloring Digraphs
by: Chalermsook, Parinya, 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)

Finding Colorings in One-Sided Expanders
by: Buhai, Rares-Darius, et al.
Published: (2025)

Faster Edge Coloring by Partition Sieving
by: Akmal, Shyan, et al.
Published: (2025)

Faster Deterministic Streaming Vertex Coloring
by: Chechik, Shiri, et al.
Published: (2026)

Tree Coloring: Random Order and Predictions
by: Frei, Fabian, et al.
Published: (2024)

Dynamic $(Δ+ 1)$ Vertex Coloring
by: Benson-Tilsen, Noam
Published: (2026)

Deterministic Online Bipartite Edge Coloring
by: Blikstad, Joakim, et al.
Published: (2024)

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

The Quasi-Polynomial Low-Degree Conjecture is False
by: Buhai, Rares-Darius, et al.
Published: (2025)

Consistent Low-Rank Approximation
by: Woodruff, David P., et al.
Published: (2026)

A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
by: S, Ajaykrishnan E, et al.
Published: (2025)