Improved Exact Algorithms for Counting 3- and 4-Colorings

2007/08/17 by Fedor V. Fomin, Serge Gaspers, Saket Saurabh · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Computer science #Discrete mathematics #Dynamic programming #Graph #Graph Labeling and Dimension Problems #Graph coloring #Mathematics #Optimization and Search Problems #Simple (philosophy) #Theoretical computer science #Time complexity

paper · doi:10.1007/978-3-540-73545-8_9

openalex publication_date 2007/08/17 · crossref created 2007/08/17 · crossref deposited 2021/04/27 · openalex created_date 2025/10/10 · crossref indexed 2026/04/30 · openalex updated_date 2026/08/04

Citations

• 3-coloring in time
• A note on the complexity of the chromatic number problem
• Enumerating maximal independent sets with applications to graph colouring
• Pathwidth of cubic graphs and exact algorithms

Cited by

• Computing the Tutte Polynomial in Vertex-Exponential Time
• Breaking the 2ⁿ Barrier for 5-Coloring and 6-Coloring
• Graph coloring [wikipedia]