Image de couverture de livre

Sampling Proper Colorings on Line Graphs Using $(1+o(1))Δ$ Colors

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Wang, Yulin, Zhang, Chihao, Zhang, Zihan
Format:	Preprint
Publié:	2023
Sujets:	Data Structures and Algorithms Probability
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Decay of correlation for edge colorings when $q>3Δ$
par: Chen, Zejia, et autres
Publié: (2025)

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
par: Moka, Sarat, et autres
Publié: (2026)

Discrete Optimal Transport: Rapid Convergence of Simulated Annealing Algorithms
par: He, Yuchen, et autres
Publié: (2026)

Dynamic $(Δ+ 1)$ Vertex Coloring
par: Benson-Tilsen, Noam
Publié: (2026)

Improved sampling algorithms and functional inequalities for non-log-concave distributions
par: He, Yuchen, et autres
Publié: (2025)

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
par: Bhattacharya, Sayan, et autres
Publié: (2023)

Beyond Brooks: $(Δ-1)$-Coloring in Semi-Streaming
par: Flin, Maxime, et autres
Publié: (2026)

$(Δ+ 1)$ Vertex Coloring in $O(n)$ Communication
par: Flin, Maxime, et autres
Publié: (2024)

Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree
par: Carlson, Charlie, et autres
Publié: (2024)

Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity
par: Jain, Vishesh, et autres
Publié: (2026)

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

Faster Dynamic $(Δ+1)$-Coloring Against Adaptive Adversaries
par: Flin, Maxime, et autres
Publié: (2025)

Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
par: Behnezhad, Soheil, et autres
Publié: (2024)

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
par: Bhattacharya, Sayan, et autres
Publié: (2024)

Sampling Sphere Packings with Continuum Glauber Dynamics
par: Kuchukova, Aiya, et autres
Publié: (2026)

Subquadratic Counting via Perfect Marginal Sampling
par: Chen, Xiaoyu, et autres
Publié: (2026)

Even Faster $(Δ+ 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
par: Bhattacharya, Sayan, et autres
Publié: (2024)

Near-Optimal Parallel Approximate Counting via Sampling
par: Harris, David G., et autres
Publié: (2026)

Spectral Independence Beyond Total Influence on Trees and Related Graphs
par: Chen, Xiaoyu, et autres
Publié: (2024)

Rapid Mixing on Random Regular Graphs beyond Uniqueness
par: Chen, Xiaoyu, et autres
Publié: (2025)

A Sampling Lovász Local Lemma for Large Domain Sizes
par: Wang, Chunyang, et autres
Publié: (2023)

Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette Sparsification
par: Assadi, Sepehr, et autres
Publié: (2025)

On Sampling from Ising Models with Spectral Constraints
par: Galanis, Andreas, et autres
Publié: (2024)

Semirandom Planted Clique via 1-norm Isometry Property
par: Guruswami, Venkatesan, et autres
Publié: (2025)

Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near-Linear Time
par: Elkin, Michael, et autres
Publié: (2024)

Threshold Rules for the Classical Prophet Inequality
par: Zhang, Jiechen
Publié: (2026)

Above-Guarantee Algorithm for Properly Colored Spanning Trees
par: Bai, Yuhang, et autres
Publié: (2026)

Mean-field Potts and random-cluster dynamics from high-entropy initializations
par: Blanca, Antonio, et autres
Publié: (2024)

A Bicriterion Concentration Inequality and Prophet Inequalities for $k$-Fold Matroid Unions
par: Alon, Noga, et autres
Publié: (2024)

Rapid Mixing at the Uniqueness Threshold
par: Chen, Xiaoyu, et autres
Publié: (2024)

Edge-Tilting Field Dynamics: Rapid Mixing at the Uniqueness Threshold and Optimal Mixing for Swendsen-Wang Dynamics
par: Chen, Xiaoyu, et autres
Publié: (2026)

Coloring 3-Colorable Graphs with Low Threshold Rank
par: Hsieh, Jun-Ting
Publié: (2025)

Exact and Efficient Sampling from Dynamic Discrete Distributions with Finite-Precision Weights
par: Hafner, Lilith Orion, et autres
Publié: (2025)

A Unified Construction of Streaming Sketches via the Lévy-Khintchine Representation Theorem
par: Pettie, Seth, et autres
Publié: (2024)

Universal Perfect Samplers for Incremental Streams
par: Pettie, Seth, et autres
Publié: (2024)

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
par: Bansal, Nikhil, et autres
Publié: (2026)

Sampling Colorings with Fixed Color Class Sizes
par: Kuchukova, Aiya, et autres
Publié: (2026)

Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $Δ$-Coloring
par: Assadi, Sepehr, et autres
Publié: (2022)

Revisit the Partial Coloring Method: Prefix Spencer and Sampling
par: Cai, Dongrun, et autres
Publié: (2024)

Efficient Parallel $(Δ+1)$-Edge-Coloring
par: Elkin, Michael, et autres
Publié: (2026)