Approximating the chromatic polynomial of a graph

DOI10.1007/3-540-57899-4_53zbMath1528.68307OpenAlexW1536122883MaRDI QIDQ6143977

Nai-Wei Lin

Publication date: 5 January 2024

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-57899-4_53

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• On rigid circuit graphs
• Ordering conjunctive queries
• Triangulated graphs and the elimination process
• On Approximation Algorithms for # P
• Algorithmic Aspects of Vertex Elimination on Graphs
• Reducibility among Combinatorial Problems
• Bounds for the chromatic number of a graph
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

This page was built for publication: Approximating the chromatic polynomial of a graph