A space improved algorithm for chromatic number

DOI10.1016/J.TCS.2025.115584MaRDI QIDQ6888790zbMATH OpenFDO

Authors Pu Wu, Huanyu Gu, Huiqin Jiang, Zehui Shao, Jin Xu

Publication date 5 December 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115584

zbMATH Keywords

exact algorithmsgraph algorithmsgraph coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number
• A note on the complexity of the chromatic number problem
• A still better performance guarantee for approximate graph coloring
• An algorithm for the chromatic number of a graph
• Covering and Packing in Linear Space
• Enumerating maximal independent sets with applications to graph colouring.
• Exact algorithms for exact satisfiability and number of perfect matchings
• Families with infants: speeding up algorithms for NP-hard problems using FFT
• Faster graph coloring in polynomial space
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• Improved Exact Algorithms for Counting 3- and 4-Colorings
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Recent Advances in Constraints
• Saving space by algebraization
• Set partitioning via inclusion-exclusion
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• Worst-case time bounds for coloring and satisfiability problems

This page was built for publication: A space improved algorithm for chromatic number

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