Approximating the chromatic polynomial of a graph

DOI10.1007/3-540-57899-4_53MaRDI QIDQ6143977zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 4087683
• Approximating the chromatic polynomial
• The computation of chromatic polynomials
• scientific article; zbMATH DE number 1409207

Cites work

• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Bounds for the chromatic number of a graph
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 47595 (Why is no real title available?)
• On Approximation Algorithms for # P
• On rigid circuit graphs
• Ordering conjunctive queries
• Reducibility among combinatorial problems
• The complexity of computing the permanent
• Triangulated graphs and the elimination process

Cited in

(1)

• On the hardness of approximating the chromatic number

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

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