Computing Bichromatic Triangle Polynomials via Edge Contraction

Abstract

We introduce the bichromatic triangle polynomial P G Δ ( k ) , a chromatic invariant that counts vertex colorings of a graph in which every designated triangular face uses exactly two colors. This polynomial refines classical chromatic counting by imposing local constraints on faces rather than edges, connecting naturally to the theory of mixed hypergraphs. We develop a recursive algorithm for computing P G Δ ( k ) based on a triangle-contraction identity: decomposing along a triangle { u , v , w } by contracting each of its three edges yields a four-term relation analogous to the classical deletion-contraction formula for chromatic polynomials. The algorithm applies to any graph equipped with triangle constraints, including 2-trees, maximal outerplanar graphs, and partially constrained structures. We prove correctness via inclusion-exclusion, analyze complexity, and illustrate the method on fans, bowties, and wheels.