Approximating the chromatic polynomial

MaRDI QIDQ2799869zbMATH OpenFDO

Authors Yvonne Kemper, Isabel Beichl

Publication date 13 April 2016

Published in Congressus Numerantium (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.04883

zbMATH Keywords

broken circuit algorithmfalling factorial algorithm

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph polynomials (05C31) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

The authors present two algorithms that approximate the coefficients of the classic chromatic polynomial of (random) graphs with relatively large orders. One of their algorithms is an improvement of the common broken circuit algorithm while the other, the falling factorial algorithm, is faster with low errors when compared to those of Li's and Knuth's.

Recommendations

• scientific article; zbMATH DE number 4087683
• An improved algorithm for approximating the chromatic number of \(G_{n,p}\)
• scientific article; zbMATH DE number 140132
• scientific article; zbMATH DE number 1962838
• scientific article; zbMATH DE number 205347

Cited in

(11)

• A matrix method for chromatic polynomials
• Using thresholds to compute chromatic polynomials.
• New approximation guarantee for chromatic number
• scientific article; zbMATH DE number 4181365 (Why is no real title available?)
• scientific article; zbMATH DE number 5626056 (Why is no real title available?)
• scientific article; zbMATH DE number 4087683 (Why is no real title available?)
• scientific article; zbMATH DE number 140132 (Why is no real title available?)
• On the hardness of approximating the chromatic number
• Approximating the chromatic polynomial of a graph
• scientific article; zbMATH DE number 7701429 (Why is no real title available?)
• An improved algorithm for approximating the chromatic number of \(G_{n,p}\)

This page was built for publication: Approximating the chromatic polynomial

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