The following are known:

  1. It is #P-complete to count the number of 3-colourings of a planar graph (with respect to randomized reductions) [1].
  2. For all $d\geq 3$, it is #P-complete to count the number of 3-colourings of a graph with maximum degree $d$ [2].

Correction (27-04-21): Result 1 is only with respect to randomized reductions (NOT deterministic reductions) in both Barbanchon [1] and Hunt et al. (unpublished work I think; details of construction appears in other papers).

What about the complexity of counting the number of 3-colourings of a planar bounded degree graph $G$?
(say, $\Delta(G)\leq 3$ or $\Delta(G)\leq 4$)

It is a bonus if bipartiteness (or girth) also comes into the picture. Counting 3-colouring of a bipartite graph is #P-complete [3]. Result 2 above is improved to triangle-free graphs of maximum degree $d$ by Greenhill [4].

[1] Barbanchon, Régis, On unique graph 3-colorability and parsimonious reductions in the plane, Theor. Comput. Sci. 319, No. 1-3, 455-482 (2004). ZBL1043.05043.

[2] Bubley, Russ; Dyer, Martin; Greenhill, Catherine; Jerrum, Mark, On approximately counting colorings of small degree graphs, SIAM J. Comput. 29, No. 2, 387-400 (1998). ZBL0937.05041.

[3] Linial, Nathan, Hard enumeration problems in geometry and combinatorics, SIAM J. Algebraic Discrete Methods 7, 331-335 (1986). ZBL0596.68041.

[4] Greenhill, Catherine, The complexity of counting colourings and independent sets in sparse graphs and hypergraphs, Comput. Complexity 9, No. 1, 52-72 (2000). ZBL0963.68082.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.