Cover Image

Online Coloring for Graphs of Large Odd Girth

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Yoneda, Hirotaka, Yoneda, Masataka
Format:	Preprint
Published:	2026
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 Graph Coloring for $k$-Colorable Graphs
by: Kawarabayashi, Ken-ichi, et al.
Published: (2025)

Better coloring of 3-colorable graphs
by: Kawarabayashi, Ken-ichi, et al.
Published: (2024)

Girth Approximations in the CONGEST Model
by: Chechik, Shiri, et al.
Published: (2026)

On the Parameterized Complexity of Odd Coloring
by: Bhyravarapu, Sriram, et al.
Published: (2025)

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

Sequentially Swapping Tokens: Further on Graph Classes
by: Kiya, Hironori, et al.
Published: (2022)

Algorithms for Optimally Shifting Intervals under Intersection Graph Models
by: Honorato-Droguett, Nicolás, et al.
Published: (2023)

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

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

Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs
by: Baumecker, Malte, et al.
Published: (2025)

Quantum Approximate Optimization Algorithms for Maximum Cut on Low-Girth Graphs
by: Li, Tongyang, et al.
Published: (2024)

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

Online Edge Coloring is (Nearly) as Easy as Offline
by: Blikstad, Joakim, et al.
Published: (2024)

Online Graph Embedding in Star Graphs
by: Dallot, Julien, et al.
Published: (2026)

On the Complexity of the Odd-Red Bipartite Perfect Matching Polytope
by: Nägele, Martin, et al.
Published: (2026)

Preprocessing to Reduce the Search Space for Odd Cycle Transversal
by: Jansen, Bart M. P., et al.
Published: (2024)

Tight Bounds for Constant-Round Domination on Graphs of High Girth and Low Expansion
by: Lenzen, Christoph, et al.
Published: (2024)

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

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

Online Firefighting on Cactus Graphs
by: Hugen, Max, et al.
Published: (2025)

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

Online Matching in Geometric Random Graphs
by: Sentenac, Flore, et al.
Published: (2023)

Dynamic Graph Coloring: Sequential, Parallel, and Distributed
by: Ghaffari, Mohsen, 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)

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)

Odd and Even Harder Problems on Cycle-Factors
by: Hörsch, Florian, et al.
Published: (2025)

The Complexity of Maximal/Closed Frequent Tree Mining for Bounded Height Trees
by: Komoto, Kenta, et al.
Published: (2026)

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

Edge Arrival Online Matching: The Power of Free Disposal on Acyclic Graphs
by: Jiang, Tianle, et al.
Published: (2024)

On the Complexity of Minimising the Moving Distance for Dispersing Objects
by: Honorato-Droguett, Nicolás, et al.
Published: (2025)

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

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

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

Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints
by: Kobayashi, Yasuaki, et al.
Published: (2023)

Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
by: Dudeja, Aditi, et al.
Published: (2024)

A Linear-Time Algorithm for Finding an Odd Cycle Through Two Specified Vertices
by: Kano, Takumi, et al.
Published: (2026)

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

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