Article
Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7
Discrete Applied Mathematics
Publication Date
7-31-2021
Document Type
Article
DOI
10.1016/j.dam.2021.03.019
Abstract
Let G be an n-vertex graph with maximum degree Δ(G) and minimum degree δ(G). We give algorithms with complexity O(1.3158n−0.7Δ(G)) and O(1.32n−0.73Δ(G)) that determines if G is 3-colorable, when δ(G)≥8 and δ(G)≥7, respectively.
Funding Number
CMMI-1727743
Funding Sponsor
National Science Foundation
Keywords
- Algorithms,
- Complexity,
- Proper coloring
Citation Information
Nicholas Crawford, Sogol Jahanbekam and Katerina Potika. "Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7" Discrete Applied Mathematics Vol. 298 (2021) p. 80 - 83 Available at: http://works.bepress.com/aikaterini-potika/61/