On the Number of $k$-Proper Connected Edge and Vertex Colorings of Graphs

Discrete and Computational Geometry, Graphs, and Games

Abstract

An edge (resp. vertex) coloring of a graph using a palette of $w$ colors is called a $k$-proper connected (resp. vertex-$k$-proper connected) $w$-coloring if and only if there exist at least $k$ vertex disjoint paths between all pairs of vertices having no two adjacent edges (resp. vertices) of the same color. In this work, we characterize the hardness of counting and approximately counting $k$-proper connected and vertex-$k$-proper connected colorings of graphs under color palette cardinality, vertex degree, bipartiteness, and planarity restrictions. In particular, we show that the problem of counting $k$-proper connected $(w=2)$-colorings and vertex-$k$-proper connected $(w=2)$-colorings of bipartite graphs is $\#P$-complete $\forall k \in \mathbb{N}_{>0}$, and that these results hold for subcubic bipartite planar graphs in the $k=1$ case. With regard to approximate counting, among other findings we show that a Fully Polynomial-time Randomized Approximation Scheme (FPRAS) for counting $k$-proper connected $(w=2)$-colorings and vertex-$k$-proper connected $(w=2)$-colorings of bipartite graphs, for any $k \in \mathbb{N}_{>0}$, implies an FPRAS for counting strong orientations and spanning connected subgraphs, respectively, of arbitrary undirected simple graphs.