Cover Image

Edge-coloring sparse graphs with $Δ$ colors in quasilinear time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Kowalik, Lukasz
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The planar edge-coloring theorem of Vizing in $O(n\log n)$ time
by: Jędrzejczak, Patryk, et al.
Published: (2025)

Decay of correlation for edge colorings when $q>3Δ$
by: Chen, Zejia, et al.
Published: (2025)

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

A linear-time algorithm for $(1+ε)Δ$-edge-coloring
by: Bernshteyn, Anton, et al.
Published: (2024)

Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros
by: Bencs, Ferenc, et al.
Published: (2024)

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

Improved bounds for coloring locally sparse hypergraphs
by: Iliopoulos, Fotis
Published: (2020)

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

Edge coloring of products of signed graphs
by: Janczewski, Robert, et al.
Published: (2023)

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

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

Kernelization for list $H$-coloring for graphs with small vertex cover
by: Piecyk, Marta, et al.
Published: (2025)

Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near-Linear Time
by: Elkin, Michael, et al.
Published: (2024)

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
by: Bhattacharya, Sayan, et al.
Published: (2024)

Coloring tournaments with few colors: Algorithms and complexity
by: Klingelhoefer, Felix, et al.
Published: (2023)

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

Simple and efficient four-cycle counting on sparse graphs
by: Burkhardt, Paul, et al.
Published: (2023)

Even Faster $(Δ+ 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
by: Bhattacharya, Sayan, et al.
Published: (2024)

Fast and Simple $(1+ε)Δ$-Edge-Coloring of Dense Graphs
by: Dhawan, Abhishek
Published: (2024)

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

Finding sparse induced subgraphs on graphs of bounded induced matching treewidth
by: Bodlaender, Hans L., et al.
Published: (2025)

Approximating maximum properly colored forests via degree bounded independent sets
by: Bai, Yuhang, et al.
Published: (2025)

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

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

Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
by: Lokshtanov, Daniel, et al.
Published: (2026)

Testing H-freeness on sparse graphs, the case of bounded expansion
by: Humeau, Samuel, et al.
Published: (2025)

Engineering Fully Dynamic Exact $Δ$-Orientation Algorithms
by: Großmann, Ernestine, et al.
Published: (2024)

$(Δ+ 1)$ Vertex Coloring in $O(n)$ Communication
by: Flin, Maxime, et al.
Published: (2024)

Beyond Brooks: $(Δ-1)$-Coloring in Semi-Streaming
by: Flin, Maxime, et al.
Published: (2026)

Quantum property testing in sparse directed graphs
by: Apers, Simon, et al.
Published: (2024)

Maximum list $r$-colorable induced subgraphs in $kP_3$-free graphs
by: Galby, Esther, et al.
Published: (2025)

Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
by: Behnezhad, Soheil, et al.
Published: (2024)

$Δ$-Motif: Parallel Subgraph Isomorphism via Tabular Operations
by: Wang, Yulun, et al.
Published: (2025)

Faster Dynamic $(Δ+1)$-Coloring Against Adaptive Adversaries
by: Flin, Maxime, et al.
Published: (2025)

Max Weight Independent Set in sparse graphs with no long claws
by: Abrishami, Tara, et al.
Published: (2023)

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

Computing largest minimum color-spanning intervals of imprecise points
by: Acharyya, Ankush, et al.
Published: (2024)

Approximating maximum-size properly colored forests
by: Bai, Yuhang, et al.
Published: (2024)

Quasilinear-time eccentricities computation, and more, on median graphs
by: Bergé, Pierre, et al.
Published: (2024)

Designing sparse temporal graphs satisfying connectivity requirements
by: Bellitto, Thomas, et al.
Published: (2026)