A note on the complexity of the chromatic number problem

1976/08/01 by Eugene L. Lawler, E.L. Lawler · 14 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Chromatic scale #Combinatorics #Computational complexity theory #Computer science #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Mathematics #Theoretical computer science

paper · doi:10.1016/0020-0190(76)90065-x

crossref issued 1976/08/01 · crossref published 1976/08/01 · crossref published-print 1976/08/01 · openalex publication_date 1976/08/01 · crossref created 2002/10/07 · crossref deposited 2019/04/09 · openalex created_date 2025/10/10 · crossref indexed 2026/01/30 · openalex updated_date 2026/07/23

Citations

• A New Algorithm for Generating All the Maximal Independent Sets

Cited by

• Computing the Tutte Polynomial in Vertex-Exponential Time
• Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
• Exact Algorithms for Treewidth and Minimum Fill-In
• Complexity of Grundy Coloring and Its Variants
• Enumerating maximal independent sets with applications to graph colouring
• 3-coloring in time
• Improved Exact Algorithms for Counting 3- and 4-Colorings
• Breaking the 2ⁿ Barrier for 5-Coloring and 6-Coloring
• On Problems as Hard as CNFSAT
• A measure & conquer approach for the analysis of exact algorithms
• Improved edge-coloring with three colors
• Combinatorial bounds via measure and conquer
• Graph coloring [wikipedia]
• Maximal independent set [wikipedia]