Improved Exact Algorithms for Counting 3- and 4-Colorings

DOI10.1007/978-3-540-73545-8_9zbMATH Open1206.05041OpenAlexW1598159863WikidataQ56269090 ScholiaQ56269090MaRDI QIDQ3608832FDOQ3608832

Serge Gaspers, Saket Saurabh, Fedor V. Fomin

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)

Cited In (8)

• Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds
• Enumeration of minimal tropical connected sets
• Colorings with few colors: counting, enumeration and combinatorial bounds
• Exponential-time quantum algorithms for graph coloring problems
• Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7
• Enumerating the edge-colourings and total colourings of a regular graph
• Exact algorithms for counting 3-colorings of graphs
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.

   Recommendations

• Exact algorithms for counting 3-colorings of graphs 👍 👎
• Colorings with few colors: counting, enumeration and combinatorial bounds 👍 👎
• Title not available (Why is that?) 👍 👎
• Coloring \(k\)-colorable graphs using smaller palettes 👍 👎
• Small Maximal Independent Sets and Faster Exact Graph Coloring 👍 👎

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)