Distributed coloring in sparse graphs with fewer colors
From MaRDI portal
Publication:2335690
zbMath1427.05121MaRDI QIDQ2335690
Pierre Aboulker, Marthe Bonamy, Louis Esperet, Nicolas Bousquet
Publication date: 15 November 2019
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i4p20
Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Distributed algorithms (68W15) Density (toughness, etc.) (05C42)
Related Items (4)
Distributed algorithms, the Lovász local lemma, and descriptive combinatorics ⋮ Local Hadwiger's conjecture ⋮ Local certification of graphs on surfaces ⋮ Local mending
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Five-list-coloring graphs on surfaces. II: A linear bound for critical graphs in a disk.
- List colourings of planar graphs
- Locally planar graphs are 5-choosable
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
- The non-existence of colorings
- Five-coloring maps on surfaces
- Every planar graph is 5-choosable
- The Moore bound for irregular graphs
- The chromatic numbers of graph bundles over cycles
- The local nature of \(\Delta\)-coloring and its algorithmic applications
- A not 3-choosable planar graph without 3-cycles
- Chromatic numbers of quadrangulations on closed surfaces
- Parallel Symmetry-Breaking in Sparse Graphs
- Locality in Distributed Graph Algorithms
- Hyperbolic families and coloring graphs on surfaces
- Dirac's map-color theorem for choosability
- On the Complexity of Distributed Network Decomposition
- Distributed Graph Coloring: Fundamentals and Recent Developments
- Improved Distributed Delta-Coloring
- An optimal distributed (Δ+1)-coloring algorithm?
- Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL model
- Distributed (∆+1)-coloring in sublogarithmic rounds
- Decomposition of Finite Graphs Into Forests
This page was built for publication: Distributed coloring in sparse graphs with fewer colors
