Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T13:37:38.616Z Has data issue: false hasContentIssue false

The Complexity of Counting Colourings of Subgraphs of the Grid

Published online by Cambridge University Press:  07 April 2006

G. E. FARR
Affiliation:
School of Computer Science and Software Engineering, Monash University (Clayton Campus), Clayton, Victoria 3800, Australia (e-mail: graham.farr@infotech.monash.edu.au)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

It is well known that counting $\lambda$-colourings ($\lambda\geq 3$) is #P-complete for general graphs, and also for several restricted classes such as bipartite planar graphs. On the other hand, it is known to be polynomial time computable for graphs of bounded tree-width. There is often special interest in counting colourings of square grids, and such graphs can be regarded as borderline graphs of unbounded tree-width in a specific sense. We are thus motivated to consider the complexity of counting colourings of subgraphs of the square grid. We show that the problem is #P-complete when $\lambda\geq 3$. It remains #P-complete when restricted to induced subgraphs with maximum degree 3.

Information

Type
Paper
Copyright
2006 Cambridge University Press