Hostname: page-component-8448b6f56d-sxzjt Total loading time: 0 Render date: 2024-04-24T06:21:52.103Z 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)

Abstract

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.

Type
Paper
Copyright
2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)