Faster 3-coloring of small-diameter graphs

DOI10.1137/21M1447714MaRDI QIDQ5866453zbMATH OpenFDO

Authors Michał Dȩbsk, Marta Piecyk, Paweł Rzążewski

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

3-coloringdiametersubexponential-time algorithms

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We study the 3- extsc{Coloring} problem in graphs with small diameter. In 2013, Mertzios and Spirakis showed that for $n$-vertex diameter-2 graphs this problem can be solved in subexponential time $2^{mathcalO(sqrtnlogn)}$. Whether the problem can be solved in polynomial time remains a well-known open question in the area of algorithmic graphs theory. In this paper we present an algorithm that solves 3- extsc{Coloring} in $n$-vertex diameter-2 graphs in time $2^{mathcalO(n^{1/3}lo{g}^{2}n)}$. This is the first improvement upon the algorithm of Mertzios and Spirakis in the general case, i.e., without putting any further restrictions on the instance graph. In addition to standard branchings and reducing the problem to an instance of 2- extsc{Sat}, the crucial building block of our algorithm is a combinatorial observation about 3-colorable diameter-2 graphs, which is proven using a probabilistic argument. As a side result, we show that 3- extsc{Coloring} can be solved in time $2^{mathcalO((nlogn{)}^{2/3})}$ in $n$-vertex diameter-3 graphs. We also generalize our algorithms to the problem of finding a list homomorphism from a small-diameter graph to a cycle.

Recommendations

• Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
• Algorithms and almost tight results for 3-colorability of small diameter graphs
• Colouring graphs of bounded diameter in the absence of small cycles
• Dominating set based exact algorithms for 3-coloring
• An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs

Cites work

• A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Acyclic, star, and injective colouring: bounding the diameter
• Algorithms and almost tight results for 3-colorability of small diameter graphs
• Can they cross? and how? (the hitchhiker's guide to the universe of geometric intersection graphs)
• Clique-width for hereditary graph classes
• Coloring problems on bipartite graphs of small diameter
• Colouring graphs of bounded diameter in the absence of small cycles
• Colouring H-free graphs of bounded diameter.
• EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
• Graph minors. V. Excluding a planar graph
• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 3229576 (Why is no real title available?)
• scientific article; zbMATH DE number 7740892 (Why is no real title available?)
• Independent feedback vertex set for P₅-free graphs
• Independent feedback vertex sets for graphs of bounded diameter
• Intersection graphs of segments
• On variable-weighted exact satisfiability problems
• Parameterized algorithms
• Partitioning \(H\)-free graphs of bounded diameter
• The complexity of colouring problems on dense graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The strong perfect graph theorem
• The three-in-a-tree problem

Cited in

(8)

• Algorithms and almost tight results for 3-colorability of small diameter graphs
• Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
• Colouring graphs of bounded diameter in the absence of small cycles
• 3-coloring C₄ or C₃-free diameter two graphs
• The parameterized complexity of strong conflict-free vertex-connection colorability
• Domination in diameter-two graphs and the 2-club cluster vertex deletion parameter
• The complexity of strong conflict-free vertex-connection k-colorability
• \(C_{2k+1}\)-coloring of bounded-diameter graphs

This page was built for publication: Faster 3-coloring of small-diameter graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5866453)