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

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

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

(11)

• Coloring graphs having few colorings over path decompositions
• Enumerating the edge-colourings and total colourings of a regular graph
• An FPTAS for counting proper four-colorings on cubic graphs
• Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7
• Exponential-time quantum algorithms for graph coloring problems
• Enumeration of minimal tropical connected sets
• On the partition of 3-colorable graphs
• Exact algorithms for counting 3-colorings of graphs
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• Colorings with few colors: counting, enumeration and combinatorial bounds
• Colorings with few colors: counting, enumeration and combinatorial bounds

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)