Faster 3-Coloring of Small-Diameter Graphs

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

zbMATH Keywords

diameter; 3-coloring; subexponential-time algorithms

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C15: Coloring of graphs and hypergraphs

05C12: Distance in graphs

05C85: Graph algorithms (graph-theoretic aspects)

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