Faster 3-Coloring of Small-Diameter Graphs
From MaRDI portal
Publication:5866453
DOI10.1137/21M1447714zbMath1497.05075arXiv2104.13860MaRDI QIDQ5866453
Michał Dȩbsk, Paweł Rzążewski, Marta Piecyk
Publication date: 21 September 2022
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2104.13860
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Algorithms and almost tight results for 3-colorability of small diameter graphs
- The three-in-a-tree problem
- Coloring problems on bipartite graphs of small diameter
- The strong perfect graph theorem
- The complexity of colouring problems on dense graphs
- Graph minors. V. Excluding a planar graph
- Intersection graphs of segments
- Independent feedback vertex sets for graphs of bounded diameter
- Independent feedback vertex set for \(P_5\)-free graphs
- Partitioning \(H\)-free graphs of bounded diameter
- On variable-weighted exact satisfiability problems
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs
- Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
- EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
- Colouring H-free graphs of bounded diameter.
- Clique-width for hereditary graph classes
- Can they cross? and how?
- Parameterized Algorithms
- Acyclic, star, and injective colouring: bounding the diameter
- Colouring graphs of bounded diameter in the absence of small cycles
This page was built for publication: Faster 3-Coloring of Small-Diameter Graphs
