Subcoloring of (Unit) Disk Graphs

Let $G$ be a simple graph. We denote by $V(G)$ and $E(G)$ the set of vertices and the set of edges of $G$, respectively. When there is no ambiguity, we denote by $n$ the number of vertices of $G$, and by $m$ the number of edges of $G$. An independent set of $G$ is a set of pairwise non-adjacent vertices, and we denote by $\alpha (G)$ the independence number of $G$, i.e., the size of a maximum independent set. Similarly, a clique in $G$ is a set of pairwise adjacent vertices, and we denote by $\omega (G)$ the size of a maximum clique. Given a set $R\subseteq V(G)$, we use $G[R]$ to denote the subgraph induced by $R$, and $G-R$ to denote the graph induced by $V(G)\setminus R$. For a vertex $v\in V(G)$, we denote by $N(v)$ the open neighborhood of $v$, that is, $N(v)=\{u\in V(G)\mid uv\in E(G)\}$, and by $N[v]$ its closed neighborhood, defined as $N[v]=N(v)\cup \{v\}$.

Given an integer $t⩾1$, we denote by $K_t$ the complete graph on $t$ vertices. A graph $G$ is said to be $K_t$-free if it does not contain $K_t$ as an induced subgraph. In the special case of $t=3$, we use the term triangle-free graph instead of $K_3$-free graph. A graph $G$ is said to be a disjoint union of cliques if there exists a partition of $V(G)$ into $V_1,\mathrm{\dots },V_{\mathrm{\ell }}$ such that, for all $1⩽i⩽\mathrm{\ell }$, $V_i$ is a clique, and there are no edge between vertices in different cliques. Equivalently, $G$ is a disjoint union of cliques if it does not contain an induced path on three vertices (i.e., it is $P_3$-free).

A graph is a co-comparability if it is the intersection graph of curves from a line to a parallel line. Equivalently, a co-comparability graph is a graph that connects pairs of elements that are not comparable to each other in a partial order.

A hypergraph $H=(V,ℰ)$ consists of a set of vertices $V$ and a set of hyperedges $ℰ$, where each hyperedge is a subset of $V$. If all hyperedges have exactly $k$ vertices, the hypergraph is called $k$-uniform. For example, in a $3$-uniform hypergraph, every edge connects exactly three vertices. Similarly to graphs, we denote by $V(H)$ the set of vertices of $H$ and by $ℰ(H)$ its set of hyperedges.

Given two points $A,B\in {ℝ}^2$, we denote by $d(A,B)$ their Euclidean distance. A disk of radius $r\in ℝ$ and center $A\in {ℝ}^2$ is the set $D(A,r)=\{B\in {ℝ}^2\mid d(A,B)⩽r\}$. The diameter of such a disk is $2r$, and if a disk has diameter $1$, it is called a unit disk.

Note that the intersection of two disks $D(A,r_A)$ and $D(B,r_B)$ is non-empty if and only if $d(A,B)⩽r_A+r_B$. A (unit) disk graph is the intersection graph of (unit) disks in the plane. The set of disks ${𝒟}_G=\{D_v=D((x_v,y_v),r_v)\mid v\in V(G)\}$ of a given disk graph $G$ is called a disk representation of $G$. For a real number $h>0$, a unit disk graph $G$ is said to have height $h$ if there exists a disk representation of $G$ such that the center of every disk lies within the region $ℝ\times [0,h]$.

An interval graph is the intersection graph of intervals on the real line. The set of intervals ${ℐ}_G={\{({\mathrm{\ell }}_v,r_v)\}}_{v\in V(G)}$ is called an interval representation of $G$.

A $\lambda$-approximation algorithm is an algorithm that runs in polynomial time with respect to the instance size and returns a solution that is guaranteed, in the worst case, to be within a factor of $\lambda$ from the optimal solution.

Here we prove the first and second cases of Theorem 1. Interestingly, they highlight two differences between proper coloring and subcoloring. First, recall that any triangle-free unit disk graph is planar, and thus admits a proper $3$-coloring. Second, observe that $k$-Coloring can be solved in linear time for every $k⩾3$ in unit disk graphs of bounded height by first deciding whether the input graph has a clique of size $k$ (in which case the answer is no), and then solving the problem using a dynamic programming over a path decomposition (whose width is thus $O(k)$). We show that these two tractable cases for $3$-Coloring remain hard for $2$-Subcoloring.

Notice that this NP-hardness cannot be generalized to $k$-Subcoloring, as we saw in the previous section that the subchromatic number of any unit disk graph is at most $7$. A direct consequence of the previous result is that $k$-Subcoloring cannot be approximated in unit disk graphs within a ratio of $3/2-\epsilon$ for any $\epsilon >0$ in polynomial-time, unless P=NP.

It remains open whether 2-Subcoloring is polynomial-time solvable for unit disk graphs of height at most $1$. If so, this would imply a $2$-approximation algorithm for Subcoloring on unit disk graphs.

Using similar ideas as in the proof of the previous result, we can tackle the case of co-comparability graphs, thus proving the remaining case of Theorem 1. Recall that these graphs contain unit disk graphs of height $\sqrt{3}/2$, and can be defined as the intersection graph of curves between two parallel lines. This result solves an open problem of Broersma, Fomin, Nešetřil, and Woeginger [4]. The proof is a reduction from No Rainbow Hypergraph 3-Coloring, which has been shown to be NP-complete [5].

No Rainbow Hypergraph 3-Coloring : Input: A $3$-uniform hypergraph $H=(V,ℰ)$ with vertex set $V$ and edge set $ℰ$ and $3$ sets $A_1,A_2,A_3\subseteq V$. Question: Is there a $3$-coloring $\mu :V\to \{1,2,3\}$ such that no hyperedge $e\in ℰ$ is “rainbow” (i.e., no hyperedge contains all 3 colors) and such that for any $k\in \{1,2,3\}$ and $v\in A_k$, $\mu (v)=k$ ?

In [16], it was proven that the same problem without fixing some vertices with some color but just requiring that the $3$-coloring is surjective, is also NP-complete. We start with a straighforward lemma.

Let $A$, $B$, and $C$ be the three distinct parts of a $K_{4,4,4}$ graph, and let $\mu$ be a 3-subcoloring of this graph. Suppose, for contradiction, that there exist two vertices in different parts with the same color. W.l.o.g., assume $a\in A$ and $b\in B$ are both colored 3. Then, no other vertex $a^{\prime }\in A\setminus \{a\}$ can have color 3; otherwise, the path $ab{a}^{\prime }$ would form a monochromatic path of three vertices. Similarly, no other vertex $b^{\prime }\in B\setminus \{b\}$ can have color 3.

Now, consider part $C$. If two different vertices $c,c^{\prime }\in C$ are also colored 3, then the path $ca{c}^{\prime }$ would also form a monochromatic path of three vertices. Consequently, after removing all vertices colored 3 from the graph, each part still contains at least three vertices. This configuration yields a 2-subcoloring of $K_{3,3,3}$, which cannot exist. $◀$

We reduce from No Rainbow Hypergraph 3-Coloring. Let $H$ be a 3-uniform hypergraph with $n$ vertices $v_1,\mathrm{\dots },v_n$ and $m$ hyperedges. Let $A_1,A_2,A_3\subseteq V(H)$. We construct a co-comparability graph $G$ as follows:

1. 1.

   For each $j=1,\mathrm{\dots },m$, create two copies of $K_{n+6}$, denoted $C_j=\{c_{j,1},c_{j,2},\mathrm{\dots },c_{j,n+6}\}$ and $L_j=\{l_{j,1},l_{j,2},\mathrm{\dots },l_{j,n+6}\}$.

2. 2.

   For each $j=1,\mathrm{\dots },m-1$, add edges to form a matching between $C_j$ and $L_j$, and similarly between $L_j$ and $C_{j+1}$. Specifically, add edges $\{(c_{j,i},l_{j,i})\mid 1⩽i⩽n+6\}$ and $\{(l_{j,i},c_{j+1,i})\mid 1⩽i⩽n+6\}$.

3. 3.

   For each $j=1,\mathrm{\dots },m$, add a set of $n$ vertices $\{l_{j,i}^{\prime }\mid 1⩽i⩽n+6\}$ to $L_j$, where each $l_{j,i}^{\prime }$ is a false twin of $l_{j,i}\in L_j$. More precisely, each $l_{j,i}^{\prime }$ is adjacent to:

   • $\mathrm{■}$

     all vertices in $L_j$ except $l_{j,i}$,

   • $\mathrm{■}$

     the vertices $c_{j,i}\in C_j$ and, if , $c_{j+1,i}\in C_{j+1}$.

   Now, $L_j$ denote the set of vertices ${\bigcup }_{1⩽i⩽n}\{l_{j,i},l_{j,i}^{\prime }\}$.

4. 4.

   For each hyperedge $e_j\in ℰ(H)$, introduce a new vertex $s_j$ (the “selector” vertex).

   • $\mathrm{■}$

     Connect $s_j$ to all vertices in $L_j$, i.e., add edges $\{(s_j,u)\mid u\in L_j\}$.

   • $\mathrm{■}$

     Additionally, connect $s_j$ to the vertices $\{c_{j,i}\mid v_i\in e_j\}$ in $C_j$ that correspond to the vertices in the hyperedge $e_j$.

5. 5.

   Add a complete multipartite graph $K_{4,4,4}$ with parts $B_1$, $B_2$, and $B_3$. For each $k\in \{1,2,3\}$ and $v_i\in A_k$, add edges from $c_{1,i}$ to each vertex in $B_{\mathrm{\ell }}$ for $\mathrm{\ell }\in \{1,2,3\}\setminus \{k\}$. Additionally, add edges from $\{c_{1,n+1},c_{1,n+2}\}$ to $B_2\cup B_3$, from $\{c_{1,n+3},c_{1,n+4}\}$ to $B_1\cup B_3$, and from $\{c_{1,n+5},c_{1,n+6}\}$ to $B_1\cup B_2$.

Observe that the size of $G$ is polynomial in the size of $H$, and we also confirm that $G$ is a co-comparability graph.

In Figure 2, we illustrate a string representation for a simple example of $G$. Below, we provide a formal proof of the desired property. The class of co-comparability graphs is closed under the addition of false twins. Indeed, in any string representation of such a graph, a string can be replaced by two non-crossing strings following the original one, resulting in the creation of false twins. Therefore, to establish that $G$ is a co-comparability graph, it suffices to show that the graph obtained by contracting each pair of false twins in $G$ is a co-comparability graph.

Let $G^{\prime }$ be the graph obtained by contracting each pair of false twins $\{l_{j,i},l_{j,i}^{\prime }\}$ into a single vertex $t_{j,i}$ for all $1\le j\le m$ and $1\le i\le n+6$, and for each $k\in \{1,2,3\}$, contracting $B_k$ into a single vertex $b_k$. Define the $2m+1$ cliques of $G^{\prime }$ as $D_0,\mathrm{\dots },D_{2m}$, where $D_0=\{b_1,b_2,b_3\}$, $D_{2j-1}=C_j$, and $D_{2j}=\{t_{j,i}\mid i=1,\mathrm{\dots },n+6\}\cup \{s_j\}$ for $1\le j\le m$. Observe that every edge of $G^{\prime }$ is either within one of these cliques or between two successive cliques.

Now, consider the following order:

We will show that this ordering respects the non-edges of $G^{\prime }$. Suppose, for some $u,v,w\in V(G^{\prime })$, that $u\prec v$, $v\prec w$, $uv\notin E(G^{\prime })$, and $vw\notin E(G^{\prime })$. Assume, for contradiction, that $uw\in E(G^{\prime })$. Then, $u$ and $w$ must either belong to the same clique or to two consecutive cliques. If $u,w\in D_j$ for some $j$, then by the construction of the order, $v\in D_j$, implying $uv\in E(G^{\prime })$, a contradiction. If $u\in D_j$ and $w\in D_{j+1}$ for some $j$, then, by the ordering, $v$ must be in either $D_j$ or $D_{j+1}$. In the first case, $uv\in E(G^{\prime })$, and in the second, $vw\in E(G^{\prime })$, both contradicting the assumption. This confirms that $G^{\prime }$ respects the co-comparability ordering. $\mathrm{⊲}$

Assume that $G$ has a $3$-subcoloring $\mu$. By Lemma 8, the vertex sets $B_1$, $B_2$, and $B_3$ must each be monochromatic with three distinct colors. W.l.o.g., assume that for each $k\in \{1,2,3\}$ and every $v\in B_k$, we have $\mu (v)=k$. Now, for each $k\in \{1,2,3\}$, take $v_i\in A_k$. By construction, the vertex $c_{1,i}$ is adjacent to every vertex in $B_{\mathrm{\ell }}$ for $\mathrm{\ell }\in \{1,2,3\}\setminus \{k\}$. Therefore, $\mu (c_{1,i})=k$, as any other color assignment would form a monochromatic $P_3$ involving $c_{1,i}$ and vertices from $B_{\mathrm{\ell }}$. Applying a similar argument, we find that $\mu (c_{1,n+1})=\mu (c_{1,n+2})=1$, $\mu (c_{1,n+3})=\mu (c_{1,n+4})=2$, and $\mu (c_{1,n+5})=\mu (c_{1,n+6})=3$. In the following claim, we detail how these colors propagate throughout the graph $G$.

We prove the result by induction on $j$. The base case holds for $j=1$.

Assume, for contradiction, that $\mu (c_{j,i})=\mu (l_{j,i})=k$, and w.l.o.g., let $k=1$. This implies that no other vertex in $C_j$ or $L_j$ can have color $1$, which leads to a contradiction because, by the induction hypothesis, $C_j$ must contain at least two vertices colored $1$, namely $c_{j,n+1}$ and $c_{j,n+2}$. Thus, by symmetry, we conclude that $\mu (c_{j,i})\ne \mu (l_{j,i})$ and $\mu (c_{j,i})\ne \mu (l_{j,i}^{\prime })$.

Now, assume for contradiction that $\mu (l_{j,i})=\mu (l_{j,i}^{\prime })=k^{\prime }$, and w.l.o.g., let $k^{\prime }=2$ (with $k=1$ as before). This assumption implies that all vertices in $L_j\setminus \{l_{j,i},l_{j,i}^{\prime }\}$ cannot have color $2$. Consider indices $i_1\in \{n+1,n+2\}\setminus \{i\}$ and $i_3\in \{n+5,n+6\}\setminus \{i\}$. By the induction hypothesis, $\mu (c_{j,i_{\mathrm{\ell }}})=\mathrm{\ell }$ for $\mathrm{\ell }\in \{1,3\}$. For both $\mathrm{\ell }\in \{1,3\}$, the vertices $l_{j,i_{\mathrm{\ell }}}$ and $l_{j,i_{\mathrm{\ell }}}^{\prime }$ cannot be colored $2$ or $\mathrm{\ell }$, as that would create a monochromatic $P_3$. Consequently, we must have $\mu (l_{j,i_1})=\mu (l_{j,i_1}^{\prime })=3$ and $\mu (l_{j,i_3})=\mu (l_{j,i_3}^{\prime })=1$.

Finally, assigning any color to a remaining vertex in $L_j\setminus \{l_{j,i},l_{j,i}^{\prime },l_{j,i_1},l_{j,i_1}^{\prime },l_{j,i_3},l_{j,i_3}^{\prime }\}$ would again create a monochromatic $P_3$, which contradicts the subcoloring property of $\mu$. Therefore, we conclude that $\mu (c_{j,i})\ne \mu (l_{j,i})\ne \mu (l_{j,i}^{\prime })$.

By symmetry, we also obtain that $\mu (c_{j+1,i})\ne \mu (l_{j,i})$ and $\mu (c_{j+1,i})\ne \mu (l_{j,i}^{\prime })$, which implies $\mu (c_{j,i})=\mu (c_{j+1,i})=k$.

Notice that the same proof shows that for any $1⩽j⩽m$, $\mu (c_{j,i})\ne \mu (l_{j,i})\ne \mu (l_{j,i}^{\prime })$. $\mathrm{⊲}$

Then, we prove that the coloring of the selector vertices ensures that their neighborhood is not a rainbow.

Suppose, for contradiction, that $\mu (N[s_j]\cap C_j)=\{1,2,3\}$. Then, there exists a vertex $v\in N(s_j)\cap C_j$ such that $\mu (s_j)=\mu (v)=k$. For $k=1$, note that $v\ne c_{j,n+1}$ because $N(s_j)\subseteq C_j\setminus \{c_{j,n+1},\mathrm{\dots },c_{j,n+6}\}$. Then, the path $s_{j}v{c}_{j,n+1}$ induces a monochromatic $P_3$ of color $1$, which is a contradiction. A similar argument applies for $k=2,3$. $\mathrm{⊲}$

Let $\nu :V(H)\to \{1,2,3\}$ be defined by $\nu (v_i)=\mu (c_{1,i})$ for $1⩽i⩽n$, and we show that $\nu$ is a no-rainbow $3$-coloring of $H$. First, for any $k\in \{1,2,3\}$ and any $v_i\in A_k$, we have $\mu (c_{1,i})=k$, and thus $\nu (v_i)=k$. Next, let $e_j=\{v_{i_1},v_{i_2},v_{i_3}\}$ be a hyperedge of $H$. By Claim 12, $\mu (N(s_j)\cap C_j)\ne \{1,2,3\}$. By construction, $N(s_j)\cap C_j=\{c_{j,i_1},c_{j,i_2},c_{j,i_3}\}$, so $\mu (\{c_{j,i_1},c_{j,i_2},c_{j,i_3}\})\ne \{1,2,3\}$.

Using Claim 11 and the definition of $\nu$, we have

Thus, $\nu (e_j)\ne \{1,2,3\}$, proving that $\nu$ is a no-rainbow $3$-coloring of $H$ such that for any $k\in \{1,2,3\}$ and $v\in A_k$, $\nu (v)=k$.

Conversely, assume that $H$ has a no-rainbow $3$-coloring $\nu$ such that for any $k\in \{1,2,3\}$ and $v\in A_k$, $\nu (v)=k$. We construct a $3$-subcoloring $\mu$ of $G$ as follows:

• $\mathrm{■}$

  For each $k\in \{1,2,3\}$ and any vertex $b\in B_k$, set $\mu (b)=k$.

• $\mathrm{■}$

  For any $1⩽j⩽m$ and $1⩽i⩽n$, set $\mu (c_{j,i})=\nu (v_i)$. Let $k,k^{\prime }$ (with ) be the two colors different from $\nu (v_i)$; then set $\mu (l_{j,i})=k$ and $\mu (l_{j,i}^{\prime })=k^{\prime }$.

• $\mathrm{■}$

  For any $1⩽j⩽m$, set $\mu (c_{j,n+1})=\mu (c_{j,n+2})=1$, $\mu (c_{j,n+3})=\mu (c_{j,n+4})=2$, and $\mu (c_{j,n+5})=\mu (c_{j,n+6})=3$. For each $i\in \{n+1,\mathrm{\dots },n+6\}$, let $k,k^{\prime }$ (with ) be the two colors different from $\mu (c_{j,i})$; then set $\mu (l_{j,i})=k$ and $\mu (l_{j,i}^{\prime })=k^{\prime }$.

• $\mathrm{■}$

  For each $1⩽j⩽n$, since $\nu$ is a no-rainbow coloring of $H$, there exists a color $k\in \{1,2,3\}\setminus \nu (e_j)$. Set $\mu (s_j)=k$.

We prove that $\mu$ is indeed a $3$-subcoloring of $G$. To establish this, we need to show that no vertex in $G$ is the center of a monochromatic $P_3$.

First, no vertex in $B_1\cup B_2\cup B_3$ has a neighbor of the same color. Assume, for contradiction, that there exists a vertex $b\in B_k$ (for some $k\in \{1,2,3\}$) that has a neighbor with the same color. This neighbor must belong to $C_1$. However, if any vertex $v_i\in C_1$ is connected to $B_1\cup B_2\cup B_3$ and has color $k$, it cannot be connected to $B_k$.

Then, for any $1⩽j⩽m$, notice that any vertex $c_{j,i}\in C_j$ does not have neighbors of the same color outside $C_j$. The only vertices it neighbors outside $C_j$ are in the sets $\{l_{j-1,i},l_{j-1,i}^{\prime },l_{j,i},l_{j,i}^{\prime },s_j\}$ if $j>1$ and $\{l_{j,i},l_{j,i}^{\prime },s_j\}$ if $j=1$. By definition of $\mu$, all these vertices have colors different from $\mu (c_{j,i})$. Additionally, since $C_j$ induces a clique, $c_{j,i}$ cannot be the center of a monochromatic $P_3$.

Similarly, for any $l_{i,j}\in L_j$, all its neighbors outside $L_j$ have different colors, except for $s_j$ which can have the same color. Thus, if $l_{i,j}$ is the center of a monochromatic $P_3$ represented as $u{l}_{i,j}v$, then $\{u,v\}\subseteq L_j\cup \{s_j\}$. Since $u$ and $v$ are not adjacent, it follows that there exists $1⩽i^{\prime }⩽n+6$ such that $\{u,v\}=\{l_{j,i^{\prime }},l_{j,i^{\prime }}^{\prime }\}$; otherwise, there would be an edge between $u$ and $v$. However, this leads to the conclusion that $\mu (l_{j,i^{\prime }})=\mu (l_{j,i^{\prime }}^{\prime })$, which contradicts the definition of $\mu$.

In conclusion, we have shown that $\mu$ is indeed a $3$-subcoloring of $G$, completing the proof. $◀$

The result can be easily generalized to $k$-Subcoloring for $k⩾3$ by induction. Indeed, if $G$ is a co-comparability graph, then the graph $G^{\prime }$ obtained by taking two disjoint copies of $G$ and adding a universal vertex is also a co-comparability graph such that ${\chi }_s(G^{\prime })={\chi }_s(G)+1$. Thus, the following holds.

The only unresolved case from the original question by Broersma et al. concerns the 2-Subcoloring problem on co-comparability graphs. It seems plausible that this problem could be solved in polynomial time, given that $k$-Subcoloring is already known to be polynomially solvable for $k=2$ on chordal graphs [15] but NP-complete for $k⩾3$. Moreover, co-comparability graphs exhibit a certain lattice structure on their maximal cliques, raising the question of whether the algorithm for chordal graphs can be adapted to handle co-comparability graphs.