Improved Exact Algorithms for Counting 3- and 4-Colorings

DOI10.1007/978-3-540-73545-8_9MaRDI QIDQ3608832zbMATH OpenOpenAlexWikidataFDO

Authors Fedor V. Fomin, Serge Gaspers, Saket Saurabh

Publication date 6 March 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73545-8_9

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

Recommendations

• Exact algorithms for counting 3-colorings of graphs
• Colorings with few colors: counting, enumeration and combinatorial bounds
• scientific article; zbMATH DE number 1830756
• Coloring k-colorable graphs using smaller palettes
• Small Maximal Independent Sets and Faster Exact Graph Coloring

Cited in

(18)

• Enumerating the edge-colourings and total colourings of a regular graph
• Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7
• Exact algorithms for counting 3-colorings of graphs
• Colorings with few colors: counting, enumeration and combinatorial bounds
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• Colorings with few colors: counting, enumeration and combinatorial bounds
• An FPTAS for counting proper four-colorings on cubic graphs
• On the partition of 3-colorable graphs
• Coloring graphs having few colorings over path decompositions
• Exponential-time quantum algorithms for graph coloring problems
• Enumeration of minimal tropical connected sets
• A piecewise approach for the analysis of exact algorithms
• Counting homomorphisms in plain exponential time
• A space improved algorithm for chromatic number
• A piecewise approach for the analysis of exact algorithms
• Breaking the 2ⁿ barrier for 5-coloring and 6-coloring
• On connections between k-coloring and Euclidean k-means
• A faster algorithm for the 4-coloring problem

This page was built for publication: Improved Exact Algorithms for Counting 3- and 4-Colorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3608832)