The Complexity of Counting Colourings of Subgraphs of the Grid

DOI10.1017/S0963548305007364MaRDI QIDQ5479031zbMATH OpenOpenAlexFDO

Authors Graham Farr

Publication date 6 July 2006

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548305007364

zbMATH Keywords

graphs of bounded tree-width

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The complexity of some graph colouring problems
• Approximately counting \(H\)-colourings is \(\#\mathrm{BIS}\)-hard
• scientific article; zbMATH DE number 1445311
• On some coloring problems in grids
• The complexity of counting edge colorings for simple graphs

Cited in

(7)

• The complexity of some graph colouring problems
• On some coloring problems in grids
• The complexity of counting edge colorings for simple graphs
• How many ways can you color your turkey? Counting the proper colorings of a grid graph
• Short certificates for chromatic equivalence
• The complexity of grid coloring
• A little statistical mechanics for the graph theorist

This page was built for publication: The Complexity of Counting Colourings of Subgraphs of the Grid

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