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

DOI10.1016/j.dam.2021.03.019OpenAlexW3152555039MaRDI QIDQ2028085

Sogol Jahanbekam, Katerina Potika, Nicholas Crawford

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

complexityalgorithmsproper coloring

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• A note on the complexity of the chromatic number problem
• Algorithmic complexity of list colorings
• Set Partitioning via Inclusion-Exclusion
• Improved Exact Algorithms for Counting 3- and 4-Colorings
• On the hardness of approximating minimization problems
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• 3-coloring in time
• An algorithm for the chromatic number of a graph

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