TITLE:
Computing Bichromatic Triangle Polynomials via Edge Contraction
AUTHORS:
Julian Allagan, Gabrielle Morgan, Shawn Langley
KEYWORDS:
Graph Coloring, Chromatic Polynomial, Triangulated Graph, Edge Contraction, Recursive Algorithm, Mixed Hypergraph
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.16 No.1,
January
22,
2026
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.