Julian Allagan, Gabrielle Morgan, Shawn Langley
Department of Mathematics, Computer Science, and Engineering Technology, Elizabeth City State University, Elizabeth City, NC, USA.
DOI: 10.4236/ojdm.2026.161001   PDF    HTML   XML   99 Downloads   510 Views   Citations

Abstract

We introduce the bichromatic triangle polynomial $P_G^{\Delta }\left(k\right)$ , 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^{\Delta }\left(k\right)$ based on a triangle-contraction identity: decomposing along a triangle $\left\{u,v,w\right\}$ 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.

Keywords

Graph Coloring, Chromatic Polynomial, Triangulated Graph, Edge Contraction, Recursive Algorithm, Mixed Hypergraph

Share and Cite:

1. Introduction

The chromatic polynomial ${\chi }_G\left(k\right)$ of a graph $G$ counts proper vertex colorings using at most $k$ colors. Introduced by Birkhoff [1] in connection with the four-color problem, it has become a central object in algebraic combinatorics with connections to statistical mechanics, knot theory, and algebraic geometry [2]-[4]. Recent work has explored the distribution and density of chromatic roots [5] [6], computational methods for special graph classes [7], and systematic frameworks for deletion-contraction algorithms [8].

The classical method for computing ${\chi }_G\left(k\right)$ is the deletion-contraction algorithm. For any edge $e=\left\{u,v\right\}$ , one has

${\chi }_G\left(k\right)={\chi }_{G-e}\left(k\right)-{\chi }_{G/e}\left(k\right),$ (1)

where $G-e$ denotes deletion of $e$ and $G/e$ denotes contraction, that is, identification of the endpoints $u$ and $v$ into a single vertex. This identity reduces computation to smaller graphs until one reaches edgeless graphs, for which ${\chi }_{{\overline{K}}_n}\left(k\right)=k^n$ .

In this paper, we study the bichromatic triangle polynomial $P_G^{\Delta }\left(k\right)$ , which counts vertex colorings of a triangulated graph in which every designated triangular face uses exactly two colors. This constraint arises naturally in several contexts. In face-coloring problems and map enumeration, one often seeks colorings with specific local properties on faces [9] [10]. More significantly, the bichromatic constraint connects to the theory of mixed hypergraphs introduced by Voloshin [11], where hyperedges may carry either “at least two colors” (D-edges) or “at most one color” (C-edges) constraints. Recent work has demonstrated applications of mixed hypergraph coloring to practical scheduling and frequency assignment problems [12]. The bichromatic condition—exactly two colors on a triangle—can be viewed as the intersection of a D-constraint and a cardinality bound, representing a refinement of mixed hypergraph coloring. Allagan [13] studied chromatic polynomials of mixed hypergraphs built from triangulated structures, and the present work extends that line of investigation by providing a systematic recursive algorithm.

Unlike proper colorings, bichromatic colorings do not require adjacent vertices to differ; the constraint is on triangular faces rather than edges. Our main contribution is a triangle-contraction identity that generalizes deletion-contraction to this setting. Rather than decomposing along a single edge, we decompose along a triangle $\tau =\left\{u,v,w\right\}$ by considering all three edge contractions $G/\left(u\equiv v\right)$ , $G/\left(v\equiv w\right)$ , and $G/\left(w\equiv u\right)$ , together with the triple contraction $G/\left(u\equiv v\equiv w\right)$ . The resulting four-term identity (Theorem 1) enables recursive computation of $P_G^{\Delta }\left(k\right)$ for any triangulated graph.

The class of graphs to which our algorithm applies is broad. It includes 2-trees, which are built recursively by attaching triangles along edges and arise in the study of chordal graphs and tree-decompositions [14]. It includes maximal outerplanar graphs (MOPs), whose interior faces are all triangles and which model various network structures. Recent advances in understanding chromatic polynomials of planar triangulations [15] and counting colorings in triangle-constrained graphs [16] have highlighted the importance of studying face-based coloring constraints. More generally, any simple graph equipped with a designated collection of triangle constraints falls within scope, including partially constrained structures where only some triangles carry the bichromatic requirement.

The paper is organized as follows. Section 2 establishes notation and defines the bichromatic triangle polynomial. Section 3 proves the triangle-contraction identity via inclusion-exclusion and establishes a formal quotient-coloring correspondence. Section 4 describes the recursive algorithm and proves its correctness. Section 5 illustrates the method on several families of graphs and Section 6 concludes with directions for future work.

2. Preliminaries

We work with graphs endowed with a distinguished system of local constraints. For the main results, these constraints are induced by selected triangles, but contractions naturally generate edge constraints as well.

[Triangle-constrained graph] A triangle-constrained graph is a triple $\left(G,\mathcal{T},ℰ\right)$ , where $G=\left(V,E\right)$ is a finite simple graph, $\mathcal{T}\subseteq \left(\begin{array}{c}V\\ 3\end{array}\right)$ is a set of triangles (3-cliques) called triangle constraints, and $ℰ\subseteq \left(\begin{array}{c}V\\ 2\end{array}\right)$ is a set of unordered vertex pairs called edge constraints. When $ℰ=\varnothing$ , we write $\left(G,\mathcal{T}\right)$ and refer to it informally as a triangulated graph in the sense of “graph equipped with constrained triangular faces,” not in the sense of chordal graphs or planar triangulations.

[Bichromatic colorings] Let $\left(G,\mathcal{T},ℰ\right)$ be triangle-constrained and $k\ge 2$ a positive integer. A $k$ -coloring is a map $c:V\left(G\right)\to \left\{1,\cdots ,k\right\}$ . A triangle $\tau =\left\{u,v,w\right\}\in \mathcal{T}$ is bichromatic under $c$ if $\left|\left\{c\left(u\right),c\left(v\right),c\left(w\right)\right\}\right|=2$ , meaning exactly two distinct colors appear among its vertices. An edge constraint $\left\{x,y\right\}\in ℰ$ is satisfied if $c\left(x\right)\ne c\left(y\right)$ . A coloring is valid if every triangle in $\mathcal{T}$ is bichromatic and every edge constraint in $ℰ$ is satisfied.

[Bichromatic triangle polynomial] The bichromatic triangle polynomial of $\left(G,\mathcal{T},ℰ\right)$ is

$P_{\left(G,\mathcal{T},ℰ\right)}^{\Delta }\left(k\right):=\#\left\{c:V\left(G\right)\to \left\{1,\cdots ,k\right\}|c\text{is}\text{valid}\right\}.$

When the constraint system is clear from context, we abbreviate this as $P_G^{\Delta }\left(k\right)$ .

In contrast with the chromatic polynomial, adjacency in $G$ does not by itself impose any restriction: edges in $E\backslash ℰ$ are unconstrained and may be monochromatic. All combinatorial structure is carried by $\left(\mathcal{T},ℰ\right)$ .

We next formalize the effect of contracting vertices on the constraint system.

[Quotient graph and induced constraints] Let $\left(G,\mathcal{T},ℰ\right)$ be triangle-constrained and $S\subseteq V\left(G\right)$ a nonempty subset. The quotient graph $G/S$ is obtained by identifying all vertices of $S$ to a single vertex $\sigma$ , redirecting incident edges to $\sigma$ , and deleting loops and parallel edges to keep the graph simple. Let $\varphi :V\left(G\right)\to V\left(G/S\right)$ be the natural surjection. We write $G/\left(u\equiv v\right)$ for $G/\left\{u,v\right\}$ and $G/\left(u\equiv v\equiv w\right)$ for $G/\left\{u,v,w\right\}$ .

The induced constraint system on $G/S$ is defined as follows. For each triangle $\tau =\left\{x,y,z\right\}\in \mathcal{T}$ , let ${\tau }^{\prime }=\varphi \left(\tau \right)$ . If $\left|{\tau }^{\prime }\right|=3$ , then ${\tau }^{\prime }$ is added to the new triangle set ${\mathcal{T}}_S$ . If $\left|{\tau }^{\prime }\right|=2$ , the bichromatic condition reduces to an edge constraint requiring the two vertices to differ, so ${\tau }^{\prime }$ is added to ${ℰ}_S$ . If $\left|{\tau }^{\prime }\right|=1$ , the constraint becomes vacuous and is discarded. Similarly, each edge constraint $\left\{x,y\right\}\in ℰ$ with $\left|\left\{\varphi \left(x\right),\varphi \left(y\right)\right\}\right|=2$ is added to ${ℰ}_S$ . The resulting triangle-constrained graph is denoted $\left(G/S,{\mathcal{T}}_S,{ℰ}_S\right)$ .

By construction, every valid coloring of $\left(G,\mathcal{T},ℰ\right)$ that is constant on $S$ corresponds bijectively to a valid coloring of the quotient $\left(G/S,{\mathcal{T}}_S,{ℰ}_S\right)$ , and conversely.

3. The Triangle-Contraction Identity

The following theorem provides the foundation for our recursive algorithm.

Theorem 1 (Triangle-contraction identity). Let $\left(G,\mathcal{T}\right)$ be a triangulated graph with $\left|\mathcal{T}\right|\ge 1$ , and let $\tau =\left\{u,v,w\right\}\in \mathcal{T}$ be a constrained triangle. Define $\left(G^{\prime },{\mathcal{T}}^{\prime }\right)$ by releasing the constraint on $\tau$ , that is, ${\mathcal{T}}^{\prime }=\mathcal{T}\backslash \left\{\tau \right\}$ . Then

$P_G^{\Delta }\left(k\right)=P_{G^{\prime }/\left(u\equiv v\right)}^{\Delta }\left(k\right)+P_{G^{\prime }/\left(v\equiv w\right)}^{\Delta }\left(k\right)+P_{G^{\prime }/\left(w\equiv u\right)}^{\Delta }\left(k\right)-3P_{G^{\prime }/\left(u\equiv v\equiv w\right)}^{\Delta }\left(k\right).$ (2)

The proof relies on a formal correspondence between colorings satisfying vertex equalities and colorings of quotient graphs.

Lemma 2 (Quotient-coloring correspondence). Let $\left(G,\mathcal{T}\right)$ be a triangulated graph and $\tau =\left\{u,v,w\right\}\in \mathcal{T}$ . Let $\left(G^{\prime },{\mathcal{T}}^{\prime }\right)$ be obtained by releasing $\tau$ , and let ${\mathcal{C}}^{\prime }$ denote the set of all colorings bichromatic for $\left(G^{\prime },{\mathcal{T}}^{\prime }\right)$ . Define $A:=\left\{c\in {\mathcal{C}}^{\prime }:c\left(u\right)=c\left(v\right)\right\}$ , $B:=\left\{c\in {\mathcal{C}}^{\prime }:c\left(v\right)=c\left(w\right)\right\}$ , and $C:=\left\{c\in {\mathcal{C}}^{\prime }:c\left(w\right)=c\left(u\right)\right\}$ . Then $\left|A\right|=P_{G^{\prime }/\left(u\equiv v\right)}^{△}\left(k\right)$ , $\left|B\right|=P_{G^{\prime }/\left(v\equiv w\right)}^{\Delta }\left(k\right)$ , $\left|C\right|=P_{G^{\prime }/\left(w\equiv u\right)}^{\Delta }\left(k\right)$ , and $\left|A\cap B\right|=\left|B\cap C\right|=\left|C\cap A\right|=\left|A\cap B\cap C\right|=P_{G^{\prime }/\left(u\equiv v\equiv w\right)}^{\Delta }\left(k\right)$ .

Proof. We establish a bijection between colorings in $A$ and valid colorings of $G^{\prime }/\left(u\equiv v\right)$ . Let $\varphi :V\left(G^{\prime }\right)\to V\left(G^{\prime }/\left(u\equiv v\right)\right)$ be the quotient map sending $u$ and $v$ to a new vertex $\sigma$ . Given $c\in A$ , define $\tilde{c}\left(\varphi \left(x\right)\right):=c\left(x\right)$ for all $x\in V\left(G^{\prime }\right)$ ; this is well-defined since $c\left(u\right)=c\left(v\right)$ . For any constrained triangle ${\tau }^{\prime }\in {\mathcal{T}}^{\prime }$ with image ${\tau }^{″}=\varphi \left({\tau }^{\prime }\right)$ : if $\left|{\tau }^{″}\right|=3$ , bichromaticity is inherited; if $\left|{\tau }^{″}\right|=2$ , the bichromatic condition on ${\tau }^{\prime }$ forces the two vertices in ${\tau }^{″}$ to have different colors; if $\left|{\tau }^{″}\right|=1$ , no constraint applies. Thus $\tilde{c}$ is valid for the quotient.

Conversely, given a valid coloring $\tilde{c}$ of $G^{\prime }/\left(u\equiv v\right)$ , define $c\left(x\right):=\tilde{c}\left(\sigma \right)$ for $x\in \left\{u,v\right\}$ and $c\left(x\right):=\tilde{c}\left(x\right)$ otherwise. Then $c\in A$ and is bichromatic for ${\mathcal{T}}^{\prime }$ . These constructions are inverses, proving $\left|A\right|=P_{G^{\prime }/\left(u\equiv v\right)}^{\Delta }\left(k\right)$ . The arguments for $B$ and $C$ are identical.

For intersections, any two of $c\left(u\right)=c\left(v\right)$ , $c\left(v\right)=c\left(w\right)$ , $c\left(w\right)=c\left(u\right)$ imply the third, so $A\cap B=B\cap C=C\cap A=A\cap B\cap C$ . The same bijection argument with triple identification yields $\left|A\cap B\cap C\right|=P_{G^{\prime }/\left(u\equiv v\equiv w\right)}^{\Delta }\left(k\right)$ . □

Proof of Theorem 1. A coloring $c\in {\mathcal{C}}^{\prime }$ is bichromatic on $\tau$ precisely when $\left|\left\{c\left(u\right),c\left(v\right),c\left(w\right)\right\}\right|=2$ , which occurs if and only if $c$ belongs to exactly one or two of $A$ , $B$ , $C$ . By inclusion-exclusion, $\left|A\cup B\cup C\right|=\left|A\right|+\left|B\right|+\left|C\right|-\left|A\cap B\right|-\left|B\cap C\right|-\left|C\cap A\right|+\left|A\cap B\cap C\right|$ . The bichromatic colorings form $\left(A\cup B\cup C\right)\backslash \left(A\cap B\cap C\right)$ , so

$P_G^{\Delta }\left(k\right)=\left|A\right|+\left|B\right|+\left|C\right|-\left|A\cap B\right|-\left|B\cap C\right|-\left|C\cap A\right|.$

By Lemma 2, each pairwise intersection equals $P_{G^{\prime }/\left(u\equiv v\equiv w\right)}^{\Delta }\left(k\right)$ . Substituting yields the identity. □

The connection to classical deletion-contraction is clear. In (1), we decompose along a single edge using deletion and contraction. In (2), we decompose along a triangle using three edge contractions plus a correction for the triple contraction. The underlying operation is identical; what differs is the structure being decomposed.

4. The Recursive Algorithm

The triangle-contraction identity yields a recursive algorithm for computing $P_G^{\Delta }\left(k\right)$ . Given a triangulated graph $\left(G,\mathcal{T}\right)$ with at least one constraint, we choose a triangle $\tau \in \mathcal{T}$ , release its constraint to form $\left(G^{\prime },{\mathcal{T}}^{\prime }\right)$ , construct the four quotient graphs with induced constraints, and recurse. The base case occurs when $\mathcal{T}=\varnothing$ , in which case the only constraints are edges in $ℰ$ , and we count colorings satisfying these edge inequalities directly.

Theorem 3 (Correctness). Let $\left(G,\mathcal{T},ℰ\right)$ be a triangle-constrained graph. Then for all integers $k\ge 2$ , Algorithm 1 returns $P_{\left(G,\mathcal{T},ℰ\right)}^{\Delta }\left(k\right)$ .

Proof. We proceed by strong induction on $m=\left|\mathcal{T}\right|$ . If $m=0$ , there are no triangle constraints, and the algorithm directly counts colorings satisfying the edge constraints in $ℰ$ .

Assume the claim holds for all graphs with fewer than $m$ triangle constraints, where $m\ge 1$ , and let $\left(G,\mathcal{T},ℰ\right)$ have $\left|\mathcal{T}\right|=m$ . Choose $\tau =\left\{u,v,w\right\}\in \mathcal{T}$ and write ${\mathcal{T}}^{\prime }=\mathcal{T}\backslash \left\{\tau \right\}$ . The proof of Theorem 1 shows, via inclusion-exclusion, that

$P_{\left(G,\mathcal{T},ℰ\right)}^{\Delta }\left(k\right)=P_{H_1}^{\Delta }\left(k\right)+P_{H_2}^{\Delta }\left(k\right)+P_{H_3}^{\Delta }\left(k\right)-3P_{H_4}^{\Delta }\left(k\right),$

where each quotient $H_i$ has at most $m-1$ triangle constraints. The inductive hypothesis applies to all four subinstances, completing the induction. □

A vertex in a quotient is free if every constrained triangle originally containing it has either been released or collapsed to exclude it; such vertices contribute a factor of $k$ without further recursion. Each application of the identity reduces $\left|\mathcal{T}\right|$ by one and produces four subproblems, giving a recursion tree with at most $4^m$ leaves. The total complexity is $O\left(4^m\cdot \text{poly}\left(\left|V\right|\right)\right)$ , comparable to deletion-contraction’s $O\left(2^{\left|E\right|}\right)$ for sparse triangulations where $m=O\left(\left|V\right|\right)$ .

Several optimizations improve practical performance. Choosing leaf triangles—those sharing only one edge with other constrained triangles—tends to isolate free vertices. Memoization can cache results for isomorphic subproblems. For structured families such as fans, ladders, and books, the recursion reveals linear recurrences solvable via transfer matrices, bypassing exponential recursion entirely.

5. Examples

We illustrate the algorithm step-by-step on several families, using green shading for constrained triangles, red for released triangles, blue for merged vertices, and dashed lines for edges incident to free vertices.

Example 4 (The Triangle K₃). For $G=K_3=\left\{u,v,w\right\}$ with $\mathcal{T}=\left\{\left\{u,v,w\right\}\right\}$ , releasing the only constraint gives ${\mathcal{T}}^{\prime }=\varnothing$ . The three pairwise contractions yield two-vertex graphs with count $k\left(k-1\right)$ each (one edge constraint), while the triple contraction yields a single vertex with count $k$ . The identity gives

$P_{K_3}^{\Delta }\left(k\right)=k\left(k-1\right)+k\left(k-1\right)+k\left(k-1\right)-3k=3k\left(k-1\right).$

This can be verified directly: a bichromatic coloring uses exactly two colors among three vertices, so one pair shares a color. There are $\left(\begin{array}{l}3\hfill \\ 2\hfill \end{array}\right)=3$ choices for the pair, $k$ choices for their common color, and $\left(k-1\right)$ for the third, giving $3k\left(k-1\right)$ . The decomposition is illustrated in Figure 1.

Figure 1. Decomposition of $K_3$ . Red indicates the released triangle; blue vertices are merged. Each of $H_1,H_2,H_3$ has one edge constraint; $H_4$ is a single free vertex.

Example 5 (The fan F₄). Consider the fan $G=F_3$ with apex $a$ and rim vertices $v_1,v_2,v_3$ . The graph contains two triangles: $T_1=\left\{a,v_1,v_2\right\}$ (constrained) and $T_2=\left\{a,v_2,v_3\right\}$ (released).

Step 1: Initial configuration. We have $\left(G,\mathcal{T}\right)=\left(F_3,\left\{T_1,T_2\right\}\right)$ . Choose $T_2$ to release, so ${\mathcal{T}}^{\prime }=\left\{T_1\right\}$ .

Step 2: First quotient $H_1=G^{\prime }/\left(a\equiv v_2\right)$ . Merge $a$ and $v_2$ into vertex $u$ . Triangle $T_1=\left\{a,v_1,v_2\right\}$ becomes $\left\{u,v_1\right\}$ (edge constraint), and vertex $v_3$ is free. The constraint system is $\left(H_1,{\mathcal{T}}_1,{ℰ}_1\right)$ with ${\mathcal{T}}_1=\varnothing$ and ${ℰ}_1=\left\{\left\{u,v_1\right\}\right\}$ . We have ${\chi }_{K_2}\left(k\right)=k\left(k-1\right)$ , and $v_3$ contributes $k$ choices, so $P_{H_1}^{\Delta }\left(k\right)=k^2\left(k-1\right)$ .

Step 3: Second quotient $H_2=G^{\prime }/\left(v_2\equiv v_3\right)$ . Merge $v_2$ and $v_3$ into vertex $w$ . Triangle $T_1=\left\{a,v_1,v_2\right\}$ becomes $\left\{a,v_1,w\right\}$ (still a triangle constraint). The constraint system is $\left(H_2,\left\{T_1\right\},\varnothing \right)$ . By the base computation for $K_3$ , $P_{K_3}^{\Delta }\left(k\right)=3k\left(k-1\right)$ , so $P_{H_2}^{\Delta }\left(k\right)=3k\left(k-1\right)$ .

Step 4: Third quotient $H_3=G^{\prime }/\left(a\equiv v_3\right)$ . Merge $a$ and $v_3$ into vertex $s$ . Triangle $T_1=\left\{a,v_1,v_2\right\}$ becomes $\left\{s,v_1,v_2\right\}$ (still a triangle constraint). By symmetry with $H_2$ , $P_{H_3}^{△}\left(k\right)=3k\left(k-1\right)$ .

Step 5: Fourth quotient $H_4=G^{\prime }/\left(a\equiv v_2\equiv v_3\right)$ . Merge all three vertices $a,v_2,v_3$ into vertex $\sigma$ . Triangle $T_1=\left\{a,v_1,v_2\right\}$ becomes $\left\{\sigma ,v_1\right\}$ (edge constraint). The constraint system is $\left(K_2,\varnothing ,\left\{\left\{\sigma ,v_1\right\}\right\}\right)$ , so $P_{H_4}^{\Delta }\left(k\right)=k\left(k-1\right)$ .

Step 6: Combine via identity.

$\begin{array}{c}{P}_{F_3}^{\Delta }\left(k\right)=P_{H_1}^{\Delta }\left(k\right)+P_{H_2}^{\Delta }\left(k\right)+P_{H_3}^{\Delta }\left(k\right)-3P_{H_4}^{\Delta }\left(k\right)\\ =k^2\left(k-1\right)+3k\left(k-1\right)+3k\left(k-1\right)-3k\left(k-1\right)\\ =k^2\left(k-1\right)+3k\left(k-1\right)=k\left(k-1\right)\left(k+3\right).\end{array}$

For $k=2$ , this yields $P_{F_3}^{△}\left(2\right)=2\cdot 1\cdot 5=10$ . The decomposition is shown in Figure 2.

Figure 2. Decomposition of $F_3$ . Green marks $T_1$ (constrained); red marks $T_2$ (released). In $H_1$ , vertex $v_3$ is free (dashed). In $H_2,H_3$ , a constrained triangle remains. In $H_4$ , only edge constraint $\left\{\sigma ,v_1\right\}$ .

Example 6 (The bowtie). The bowtie consists of triangles $T_1=\left\{a,b,c\right\}$ and $T_2=\left\{a,d,e\right\}$ sharing only vertex $a$ . Since $T_1\cap T_2=\left\{a\right\}$ , no contraction within $T_2$ affects two vertices of $T_1$ , so $T_1$ remains intact in every quotient. In $H_1,H_2,H_3$ , one vertex from $\left\{d,e\right\}$ becomes free; in $H_4$ , only $T_1$ remains. The decomposition is illustrated in Figure 3.

Thus $P_{\text{Bowtie}}^{\Delta }\left(k\right)=3\cdot 3k^2\left(k-1\right)-3\cdot 3k\left(k-1\right)=9k{\left(k-1\right)}^2$ .

Example 7 (The wheel W₄). The wheel $W_4$ has hub $h$ and rim $v_1,v_2,v_3,v_4$ , with triangles ${\tau }_i=\left\{h,v_i,v_{i+1}\right\}$ for $i=1,2,3,4$ (indices mod 4). We release ${\tau }_1=\left\{h,v_1,v_2\right\}$ , keeping ${\mathcal{T}}^{\prime }=\left\{{\tau }_2,{\tau }_3,{\tau }_4\right\}$ constrained.

Quotient $H_1=G^{\prime }/\left(h\equiv v_1\right)$ : Merge $h$ and $v_1$ into vertex $u$ . The constraints transform as ${\tau }_2\mapsto \left\{u,v_2,v_3\right\}$ (triangle), ${\tau }_3\mapsto \left\{u,v_3,v_4\right\}$ (triangle), and ${\tau }_4\mapsto \left\{u,v_4\right\}$ (edge). Write $a=c\left(u\right)$ , $b=c\left(v_2\right)$ , $c=c\left(v_3\right)$ , $d=c\left(v_4\right)$ . We

Figure 3. Bowtie decomposition. Releasing $T_2$ preserves $T_1$ in all quotients. Dashed edge to $e$ indicates it is free.

need $\left|\left\{a,b,c\right\}\right|=2$ , $\left|\left\{a,c,d\right\}\right|=2$ , and $a\ne d$ .

If $a=c$ , then bichromaticity forces $b\ne a$ and $d\ne a$ , and the edge constraint is automatically satisfied, giving $k{\left(k-1\right)}^2$ colorings. If $a\ne c$ , then $b\in \left\{a,c\right\}$ (2 choices) and the edge constraint forces $d=c$ (1 choice), giving $2k\left(k-1\right)$ colorings. Thus $P_{H_1}^{\Delta }\left(k\right)=k{\left(k-1\right)}^2+2k\left(k-1\right)=k\left(k-1\right)\left(k+1\right)$ . By symmetry, $P_{H_3}^{△}\left(k\right)=k\left(k-1\right)\left(k+1\right)$ .

Quotient $H_2=G^{\prime }/\left(v_1\equiv v_2\right)$ : Merge $v_1$ and $v_2$ into vertex $w$ . The graph is $K_4$ on $\left\{h,w,v_3,v_4\right\}$ , but only three triangles (those containing $h$ ) are constrained: $\left\{h,w,v_3\right\}$ , $\left\{h,v_3,v_4\right\}$ , $\left\{h,v_4,w\right\}$ . The triangle $\left\{w,v_3,v_4\right\}$ is unconstrained. All valid colorings use exactly two colors: if three distinct colors appeared, some constrained triangle would contain all three (impossible for bichromatic). For each ordered pair of colors $\left(c\left(h\right),c_{\text{other}}\right)$ , there are exactly 4 valid patterns for $\left(c\left(w\right),c\left(v_3\right),c\left(v_4\right)\right)$ that make all three constrained triangles bichromatic. Thus $P_{H_2}^{\Delta }\left(k\right)=4k\left(k-1\right)$ .

Quotient $H_4=G^{\prime }/\left(h\equiv v_1\equiv v_2\right)$ : Merge $h,v_1,v_2$ into vertex $\sigma$ . Constraints become edge $\left\{\sigma ,v_3\right\}$ , triangle $\left\{\sigma ,v_3,v_4\right\}$ , and edge $\left\{\sigma ,v_4\right\}$ . Edge constraints force $c\left(\sigma \right)\ne c\left(v_3\right)$ and $c\left(\sigma \right)\ne c\left(v_4\right)$ , and bichromaticity then requires $c\left(v_3\right)=c\left(v_4\right)$ . Thus $P_{H_4}^{\Delta }\left(k\right)=k\left(k-1\right)$ .

Combining:

$\begin{array}{c}{P}_{W_4}^{\Delta }\left(k\right)=k\left(k-1\right)\left(k+1\right)+4k\left(k-1\right)+k\left(k-1\right)\left(k+1\right)-3k\left(k-1\right)\\ =k\left(k-1\right)\left[2\left(k+1\right)+4-3\right]=k\left(k-1\right)\left(2k+3\right).\end{array}$

For $k=2$ , this gives $P_{W_4}^{\Delta }\left(2\right)=2\cdot 1\cdot 7=14$ , matching direct enumeration. The decomposition is shown in Figure 4.

Figure 4. Decomposition of $W_4$ . In $H_1,H_3$ : two triangles plus edge constraint. In $H_2$ : three triangles containing $h$ , but $\left\{w,v_3,v_4\right\}$ is unconstrained (dashed).

Graph	Formula	$k=2$
$K_3$	$3k\left(k-1\right)$	6
$F_4$ (fan)	$k\left(k-1\right)\left(k+3\right)$	10
Bowtie	$9k{\left(k-1\right)}^2$	18
$W_4$ (wheel)	$k\left(k-1\right)\left(2k+3\right)$	14

6. Conclusions and Future Directions

We have presented a recursive algorithm for computing the bichromatic triangle polynomial of any triangulated graph, based on a triangle-contraction identity that extends classical deletion-contraction to face constraints. The algorithm correctly handles all configurations of triangles, including edge-sharing, vertex-sharing, and complex nested structures such as wheels.

The class of admissible graphs is broad. It includes 2-trees, which are constructed by repeatedly attaching triangles along edges and arise in the study of chordal graphs and tree-decompositions [14]. It includes maximal outerplanar graphs (MOPs), whose faces are all triangles and which model various network structures. It includes general outerplanar graphs, where we may constrain only some faces. More generally, any simple graph equipped with a partial collection of triangle constraints falls within scope, allowing application to mixed or incomplete triangulations where the bichromatic requirement applies to a designated subset of triangular faces.

The chromatic polynomial is famously an evaluation of the Tutte polynomial, ${\chi }_G\left(k\right)={\left(-1\right)}^{\left|V\right|-c\left(G\right)}{k}^{c\left(G\right)}{T}_G\left(1-k,0\right)$ , where $c\left(G\right)$ is the number of connected components of $G$ . Recent work on Tutte polynomials and their generalizations [17] [18] suggests rich connections between edge-based and face-based polynomial invariants. It is natural to ask whether $P_G^{\Delta }\left(k\right)$ admits a similar two-variable generalization. Such a polynomial would provide finer invariants for triangulated graphs and potentially connect to the rich theory of the Tutte polynomial and its extensions to hypergraphs.

Future directions include developing polynomial-time algorithms for broader graph classes. Recent progress on efficient algorithms for chromatic polynomials of chordal and outerplanar graphs [7] suggests that specialized techniques may apply to bichromatic triangle polynomials for restricted graph families. Dynamic programming on tree decompositions could yield efficient computation for graphs of bounded treewidth. Investigating algebraic properties of $P_G^{\Delta }\left(k\right)$ such as the location of roots may reveal important structural properties; recent advances in understanding chromatic roots [5] [6] provide methodological frameworks for such investigations. Extending the framework to more general face-constrained coloring problems, as explored in recent work [10], could broaden the scope of applications. Finally, exploring connections to the chromatic polynomials of mixed hypergraphs [12] in greater depth may yield both theoretical insights and practical applications in network design, scheduling, and resource allocation.

Acknowledgements

This work was supported by the U.S. Department of Education under grant number P382G240006. The authors thank the anonymous reviewers for their helpful suggestions and careful reading of the manuscript.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Birkhoff, G.D. (1912) A Determinant Formula for the Number of Ways of Coloring a Map. The Annals of Mathematics, 14, 42-46.[CrossRef]
[2]	Dong, F.M., Koh, K.M. and Teo, K.L. (2005) Chromatic Polynomials and Chromaticity of Graphs. World Scientific Publishing Co. Pte. Ltd.[CrossRef]
[3]	Stanley, R.P. (1995) A Symmetric Function Generalization of the Chromatic Polynomial of a Graph. Advances in Mathematics, 111, 166-194.[CrossRef]
[4]	Tutte, W.T. (1954) A Contribution to the Theory of Chromatic Polynomials. Canadian Journal of Mathematics, 6, 80-91.[CrossRef]
[5]	Kayll, P.M. and Perkins, W. (2019) Roots of Chromatic Polynomials of Graphs. Journal of Combinatorial Theory, Series B, 138, 264-290.
[6]	Sokal, A.D. (2021) Chromatic Roots are Dense in the Whole Complex Plane. Combinatorics, Probability and Computing, 30, 918-943.
[7]	Esperet, L. and Kang, R.J. (2021) Polynomial Algorithms for Chromatic Polynomials of Chordal Graphs and Outerplanar Graphs. Algorithmica, 83, 2139-2158.
[8]	Edwards, K. and Kang, D.Y. (2023) Computation of Graph Polynomials via Deletion-Contraction and Applications. SIAM Journal on Discrete Mathematics, 37, 1324-1349.
[9]	Baxter, R.J. (1982) Exactly Solved Models in Statistical Mechanics. Academic Press.
[10]	Li, X. and Zhang, Y. and Wang, H. (2024) Face Coloring Problems in Planar Graphs with Local Constraints. European Journal of Combinatorics, 115, Article ID: 103782.
[11]	Voloshin, V. (2002) Coloring Mixed Hypergraphs: Theory, Algorithms and Applications. American Mathematical Society.[CrossRef]
[12]	Hoang, D.T. and Lai, H.J. (2023) Mixed Hypergraph Coloring with Applications to Scheduling and Frequency Assignment. Discrete Applied Mathematics, 325, 89-102.
[13]	Allagan, J.A. (2014) Chromatic Polynomials of Mixed Hypergraphs. Australasian Journal of Combinatorics, 58, 197-213.
[14]	Bodlaender, H.L. (1998) A Partial K-Arboretum of Graphs with Bounded Treewidth. Theoretical Computer Science, 209, 1-45.[CrossRef]
[15]	Dong, F.M. and Teo, K.L. and Little, C.H.C. (2020) Chromatic Polynomials of Planar Triangulations. Discrete Mathematics, 343, Article ID: 111913.
[16]	Cameron, B. and Colbourn, C.J. (2022) Counting Colorings of Triangle-Free Graphs. Journal of Graph Theory, 99, 628-647.
[17]	Traldi, L. (2020) On the Tutte Polynomial of a Graph and Related Polynomials. Advances in Applied Mathematics, 118, Article ID: 102041.
[18]	Kostochka, A. and Luo, R. and Zhu, X. (2022) Hypergraph Coloring and the Tutte Polynomial. Journal of Combinatorial Theory, Series B, 157, 112-138.