Enumerating maximal independent sets with applications to graph colouring

2004/04/29 by Jesper Makholm Byskov · 6 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Butterfly graph #Chromatic scale #Combinatorics #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Line graph #Mathematics #Upper and lower bounds #Voltage graph

paper · doi:10.1016/j.orl.2004.03.002

openalex publication_date 2004/04/29 · crossref created 2004/04/29 · crossref issued 2004/11/01 · crossref published 2004/11/01 · crossref published-print 2004/11/01 · crossref deposited 2019/02/10 · openalex created_date 2025/10/10 · crossref indexed 2026/01/25 · openalex updated_date 2026/07/29

Citations

• A note on the complexity of the chromatic number problem
• On cliques in graphs
• A New Algorithm for Generating All the Maximal Independent Sets

Cited by

• Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
• Improved Exact Algorithms for Counting 3- and 4-Colorings
• Breaking the 2ⁿ Barrier for 5-Coloring and 6-Coloring
• A measure & conquer approach for the analysis of exact algorithms
• On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms
• Graph coloring [wikipedia]