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

DOI10.1016/J.DAM.2021.03.019OpenAlexW3152555039MaRDI QIDQ2028085FDOQ2028085

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

algorithmscomplexityproper coloring

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• 3-coloring in time
• 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 (1)

• 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)