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

DOI10.1016/J.DAM.2021.03.019OpenAlexW3152555039MaRDI QIDQ2028085FDOQ2028085

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

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

zbMATH Keywords

algorithmscomplexityproper coloring

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

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

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)