Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7

DOI10.1016/J.DAM.2021.03.019MaRDI QIDQ2028085zbMATH OpenOpenAlexFDO

Authors Nicholas Crawford, Sogol Jahanbekam, Katerina Potika

Publication date 31 May 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.12880

zbMATH Keywords

algorithmscomplexityproper coloring

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Theory of computing (68Qxx) Graph theory (05Cxx)

Recommendations

• Dominating set based exact algorithms for 3-coloring
• Coloring \(k\)-colorable graphs using smaller palettes
• An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
• Coloring -colorable graphs using relatively small palettes
• Better 3-coloring algorithms: excluding a triangle and a seven vertex path

Cites work

• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• 3-coloring in time
• A note on the complexity of the chromatic number problem
• Algorithmic complexity of list colorings
• An algorithm for the chromatic number of a graph
• Improved Exact Algorithms for Counting 3- and 4-Colorings
• On the hardness of approximating minimization problems
• Set partitioning via inclusion-exclusion
• Small Maximal Independent Sets and Faster Exact Graph Coloring

Cited in

(3)

• Algorithms and almost tight results for 3-colorability of small diameter graphs
• Dominating set based exact algorithms for 3-coloring
• Improved algorithm to determine 3-colorability of graphs with the minimum degree at least 7

This page was built for publication: Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7

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