Polychromatic $2$-Colorings with Bounded Discrepancy for Triangulations

Let $R$ and $B$ be the color classes in $\rho$. Every edge in the matching $M_Q$ has one endpoint in each color class. Let $U_R\subseteq R$ and $U_B\subseteq B$ be the unmatched vertices. Then $|R|=|M_Q|+|U_R|$ and $|B|=|M_Q|+|U_B|$. Without loss of generality, assume that $|R|\ge |B|.$ Then, $\mathrm{disc}(\chi )=|R|-|B|=|U_R|-|U_B|\le |U_R|+|U_B|=n-2|M_Q|$. $◀$

Now, to define an appropriate spanning quadrangulation with the appropriate matching, the strategy is to start with a matching $M$ in the triangulation $G$, and then show that there exists a spanning quadrangulation containing a large fraction of edges from $M$.

There is a well-known equivalence between the $4$-coloring of the vertices of a triangulation $G$ and the $3$-coloring of the edges of its dual $G^{\ast }$. Such edge-coloring induces a partition of the edges of $G^{\ast }$ into 3 perfect matchings of $G^{\ast }$. Let $E_1$, $E_2$ and $E_3$ be the sets of edges of $G$ corresponding to each of the 3 perfect matchings in $G^{\ast }$. Let $Q_i=G\setminus \{E_i\}$ for $i\in \{1,2,3\}$. We note that each $Q_i$ is a spanning quadrangulation of $G$. (see e.g. [1], [5], [6], and [12]).

Every edge of $M$ appears by construction in exactly 2 of the $Q_i$’s, which implies that one of the $Q_i$’s contains at least $\frac{2}{3}|M|$ edges of $M$. $◀$

The following is the main result of this subsection.

By Lemma 8, $G$ has a a spanning quadrangulation $Q$ that has a matching $M_Q$ of size at least $\frac{2}{3}|M|$. By Lemma 7 the proper $2$-coloring of $Q$ is a polychromatic $2$-coloring of $G$ with discrepancy at most $n-2|M_Q|\le n-\frac{4}{3}|M|$. $◀$

Follows from Theorem 9 with the matching that is guaranteed by Proposition 6. $◀$

A relevant application of Theorem 9 is to obtain a better upper bound for the discrepancy of polychromatic $2$-colorings in Delaunay triangulations, stated in the following Corollary.

It is known that Delaunay triangulations have perfect matchings [3, 10]. Then by Theorem 9, $D$ has a polychromatic $2$-coloring whose discrepancy is at most $n-\frac{4}{3}\left(\frac{n}{2}\right)$. $◀$

Observe that the bound $\frac{n}{3}$ is true for any triangulation with a perfect matching.

Let $\rho$ be the $2$-coloring that assigns $R=V_1\cup V_4$ and $B=V_2\cup V_3$. Then $r=n_1+n_4$ and $b=n_2+n_3$. We claim that $\rho$ is a polychromatic $2$-coloring. Since every face of $G$ is triangular, it contains vertices from 3 different color classes of the $4$-coloring $\chi$. Therefore, in $\rho$ every face contains at least one red and one blue vertex.

Since $n_1+n_4\ge n_2\ge n_3$, we have that $r=n_1+n_4\ge \frac{n}{3}$. Thus, if $n_1+n_4\le \frac{2n}{3}$ then $\mathrm{disc}(\rho )=|2r-n|\le \frac{n}{3}$.

If $n_1\le \frac{n}{2}$ then by applying Observation 12 we get $n_2+n_3=n-n_1-n_4\ge \frac{2n-2n_1}{3}\ge \frac{n}{3}$. Once again we get then $\mathrm{disc}(\rho )=|2r-n|\le \frac{n}{3}$. $◀$

Let $\rho$ be the polychromatic 2-coloring defined in the proof of Lemma 14. By observation 12, we know that $r=n_1+n_4\le \frac{n+2n_1}{3}$. Since $r=n_1+n_4\ge \frac{n}{2}$, we have $\mathrm{disc}(\rho )=2r-n.$ We conclude that

$◀$

The sizes of the color classes in $\chi$ meet the conditions of Lemma 14 or 15. $◀$

By the Four Color Theorem, $G$ has a proper $4$-coloring $\chi$. Let $n_1$ be the size of the largest color class of $\chi$. By Observation 17 and Proposition 4, we have $n_1\le \alpha (G)\le \frac{2n-4}{\delta (G)}$ and we can apply Theorem 16 with $s=\frac{2n-4}{\delta (G)}$. Since every planar triangulation with $n\ge 4$ vertices has minimum degree at least $3$, it follows that:

If $\delta (G)\ge 4$ then

$◀$

There is a relation between the size of a matching and the size of the maximum independent set in $G$.

We have provided an alternative proof for two theorems from [1]. Moreover, we have generalized these results by establishing an upper bound on the discrepancy of a polychromatic $2$-coloring in terms of an upper bound on the size of the largest color class in a proper $4$-coloring.

We give an upper bound for $r=n_1+s_4$ based on the following observations:

1. 1.

   Every vertex in $V_1$ is in at least $3$ faces from $F_1$ because $\delta (G)\ge 3$. Every face in $F_1$ has exactly one vertex from $V_1$. Then $3n_1\le |F_1|$.

2. 2.

   Every vertex in $S_4$ is in at least one face from $F_{234}$ by definition. Every face in $F_{234}$ has exactly one vertex in $S_4$. Then $s_4\le |F_{234}|$.

By Proposition 3, the total number of faces of $G$ is $|F_1|+|F_{234}|=2n-4$, then we conclude that:

We know that $S_4\subseteq V_4$, then $s_4\le n_4$. By Observation 12, we have $n_4\le \frac{n-n_1}{3}$, which implies that:

By adding up the equations 1 and 2, we get $4n_1+4s_4\le 3n-4$. Then $r=n_1+s_4\le \frac{3n-4}{4}$ and $\mathrm{disc}(\rho )=2r-n\le \frac{n-4}{2}$. $◀$

Some extra observations help to improve this bound. Let $G$ be a planar triangulation with $n$ vertices. Let ${\chi }_{min}$ be a proper $4$-coloring of $V(G)$ such that the difference between the sizes of the largest and the smallest color class, i.e. $n_1-n_4$, is minimum over all proper $4$-colorings of $V(G)$. From the results in Subsection 3.2 (Lemma 14), we know that if $n_1+n_4\le \frac{2n}{3}$ or $n_1\le \frac{n}{2}$, then the coloring that assigns $R=V_1\cup V_4$ and $B=V_2\cup V_3$ is polychromatic and has a discrepancy at most $\frac{n}{3}$. Thus, we may assume that $n_1>\frac{n}{2}$ and $n_1+n_4>\frac{2n}{3}$ in the following. Then, Observation 12 implies that $n_4\le \frac{n}{6}$. Therefore, we get

Let $V_1^{d=3}$ be the set of vertices in $V_1$ whose degree equals $3$ and let $V_1^{d\ge 4}=V_1\setminus V_1^{d=3}$ be those with degree at least $4$.

We refer to the faces in $F_{234}$ as good faces. We classify every essential vertex as type I if it is in exactly one good face and type II if it is in at least two good faces. For any vertex $v$ in $G$, let $N_i(v)$ be the set of neighbors of $v$ in $V_i$ for all $i\in \{1,2,3,4\}$.

Let $x\in S_4$ be an essential vertex of type I with degree $d(x)$. Since $x$ is in exactly one good face, there is exactly one vertex in $N_2(x)$ and one vertex in $N_3(x)$ that are adjacent to each other. The other $d(x)-2$ vertices are alternating between elements in $N_1(x)$ and elements in $N_2(x)\cup N_3(x)$ starting and ending with color 1 adjacent to the good face, otherwise we contradict that vertex $x$ is of type I. This implies that $\frac{d(x)-1}{2}$ of the neighbors have color 1. $◀$

We say that a connected subgraph of $G$ is $i$-$j$-alternating if it is properly $2$-colored with colors $i$ and $j$.

Let $y\in N_1(x)$. Since $d(y)=3$, $y$ is inside a separating triangle formed by $x$ and the endpoints of a $2$-$3$-edge. Then there is a $2$-$3$-edge for each vertex in $N_1(x)$ and a $2$-$3$ edge for each good face incident to $x$, all those edges together form a $2$-$3$-alternating separating cycle $C$ whose inside vertices are $x\in V_4$ and all the vertices in $N_1(x)$. Let $\mathrm{\ell }(C)$ be the length of $C$. Observe that $\mathrm{\ell }(C)$ is even and at least 4, so in the case where $x$ is of type I, exactly one of the edges in $C$ is part of a good face containing $x$ and $\mathrm{\ell }(C)-1$ edges are part of a separating triangle that contains a vertex of color 1. Then $|N_1(x)|=\mathrm{\ell }(C)-1$. Note that $d(x)=|N_1(x)|+\mathrm{\ell }(C)=2\mathrm{\ell }(C)-1\ge 2(4)-1=7$.$◀$

Let $x\in S_4$ be an essential vertex of type I. By Lemma 23, since $d(x)\ge 3$, $|N_1(x)|\ge 1$. Assume for a contradiction that every vertex in $N_1(x)$ has degree $3$. By Lemmas 23 and 24, $x$ has odd degree $d(x)\ge 7$, $|N_1(x)|=\frac{d(x)-1}{2}\ge 3$ and there is a $2$-$3$-separating alternating cycle $C$ containing exactly one vertex of color $4$, namely $x$, and $|N_1(x)|$ vertices of color $1$ in its interior. By swapping colors 1 and 4 in $C$ (Observation 26) we obtain a valid proper $4$-coloring ${\chi }^{\prime }$ whose color classes that has $n_1-|N_1(x)|+1$ vertices of color 1 and $n_4-1+|N_1(x)|$ vertices of color 4. This would decrease the difference between $n_1$ and $n_4$ and hence contradicts our choice of ${\chi }_{min}$.

We have to be careful here as color 4 may now be the largest color class in ${\chi }^{\prime }$. Hence the difference would be

where the inequality is valid by Observation 22 and Observation 26. This still contradicts our choice of ${\chi }_{min}$ in view of Observation 26. $◀$

Similar to the partition of $V_4$ in essential and non-essential vertices, we partition $V_1$ according to the faces they belong to. Let $S_1\subseteq V_1$ be the set of vertices in $V_1$ belonging to at least one face that does not contain a vertex from $S_4$. Let $s_1=|S_1|$. Let ${\overline{S}}_1=V_1\setminus S_1$ and call these vertices non-essential since they can be colored red or blue without violating the polychromatic 2-coloring property.

In the following Lemma we state an upper bound for $s_1+s_4$, which we later use to bound the discrepancy of a polychromatic $2$-coloring.

We use a discharging argument. We assign $1$ unit of charge to every face in $F_{234}$. For every vertex $y\in V_1$, we assign a charge equal to $d(y)$. Thus, the total initial charge is $|F_{234}|+|F_1|=2n-4$. Apply the transfer of charge as follows: Each face in $F_{234}$ transfers its charge to its unique vertex in $V_4$. For every vertex $y\in V_1$, if $d(y)\ge 4$, then transfer $1$ unit of charge to each of its neighbors that is in $S_4$. The total final charge is equal to the total initial charge. We analyze the final charge in the vertices of $S_1$ and $S_4$.

Let $y\in S_1$. We know $d(y)\ge 3$. If $d(y)=3$, then $y$ has final charge equal to $3$. If $d(y)=4$, then $y$ has at most one neighbour in $S_4$, otherwise it contradicts Observation 28. Therefore, the final charge is at least $3$. If $d(y)\ge 5$, then $y$ has at most $\lfloor \frac{d(y)}{2}\rfloor$ neighbors in $S_4$, since no two color 4 vertices are adjacent. Thus, the final charge of $y$ is at least $d(y)-\lfloor \frac{d(y)}{2}\rfloor =\lceil \frac{d(y)}{2}\rceil \ge \lceil \frac{5}{2}\rceil =3$.

Let $x\in S_4$ be an essential vertex. If $x$ is of type II, then it gets at least $2$ units of charge from the two faces in $F_{234}$. Assume $x$ is type I, then it gets 1 unit of charge from its incident $F_{234}$ face. By Lemma 27, $x$ is adjacent to a vertex $y\in V_1$ such that $d(y)\ge 4$, from which it gets an additional unit of charge. Thus, every vertex in $S_4$ has final charge at least $2$.

Since the total final charge is equal to the total initial charge, the final charge in $S_1\cup S_4$ is at most the total initial charge.

We know that $S_1\subseteq V_1$ and $S_4\subseteq V_4$, then $s_1\le n_1$ and $s_4\le n_4$. By Observation 12, we have $n_4\le \frac{n-n_1}{3}$, which implies that:

Multiplying by 2 both sides of (3) and adding it to (4), we get $7s_1+7s_4\le 5n-8$. Then $s_1+s_4\le \frac{5n-8}{7}$. $◀$

We know that $S_1\cup S_4\subseteq V_1\cup V_4$, and $|V_1\cup V_4|=n_1+n_4>\frac{n}{2}$. If $s_1+s_4\ge \frac{n}{2}$, then let $\rho$ be the $2$-coloring that assigns $R=S_1\cup S_4$. Otherwise, add some vertices from $\overline{S_1}\cup \overline{S_4}$ to $R$ in order to guarantee $r=|R|\ge \frac{n}{2}$. The sizes of the color classes of $\rho$ are $r=\max (s_1+s_4,\frac{n}{2})$ and $b=n-r$. Observe that $\rho$ is a polychromatic $2$-coloring and $disc(\rho )=2r-n$. By Lemma 29, $\mathrm{disc}(\rho )=2r-n\le 2\left(\frac{5n-8}{7}\right)-n=\frac{3n-16}{7}$. This finishes the proof of Theorem 20.