# Complexity of counting 3-colourings of planar bounded degree graphs

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].

References
[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.