3-colorability of graphs with minimum degree at least 6

2021/04/13 by Nicholas Crawford, Crawford, Nicholas, Sogol Jahanbekam +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.2104.06547

openalex publication_date 2021/04/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let G be an n-vertex graph and let L:V(G)→ P(\1,2,3\) be a list assignment over the vertices of G, where each vertex with list of size 3 and of degree at most 5 has at least three neighbors with lists of size 2. We can determine L-choosability of G in O(1.3196^n₃+.5n₂) time, where n_i is the number of vertices in G with list of size i for i∈ \2,3\. As a corollary, we conclude that the 3-colorability of any graph G with minimum degree at least 6 can be determined in O(1.3196^n-.5Δ(G)) time.

Related

• Improved algorithm to determine 3-colorability of graphs with the\n minimum degree at least 7
• Graphs with large minimum degree and no small odd cycles are 3-colourable
• P=NP
• 3 List Coloring Graphs of Girth at least Five on Surfaces
• A certifying algorithm for 3-colorability of P5-free graphs