On Generalized Total Colourings of Planar Graphs

Abstract.

In this paper we study generalised total colourings of graphs where the colour classes formed by vertices and edges, respectively, induce forests, while incident edges/vertices receive distinct colours. In [3] it was conjectured that for planar graphs, four colours suffice for this type of colouring. We confirm this conjecture for two infinite families of planar graphs.

1. Introduction

In this paper we study simple, loopless, undirected graphs. For all undefined graph theoretical terms we refer the reader to [6]. For a graph $G$, we will denote its set of vertices and its set of edges by $V(G)$ and $E(G)$, respectively.

The colourings we are interested in were introduced in the general context of hereditary properties, in [5]. Although we will only be concerned with one particular case of the so-called $({\cal P},{\cal Q})$-total colourings, we briefly sketch the broader context for completeness, following [4]. Let ${\cal I}$ denote the class of all graphs. A graph property is any isomorphism-closed subclass of ${\cal I}$. Let ${\cal P}$ be such a subclass. If a graph $G$ is a member of ${\cal P}$ we will say that $G$ has property ${\cal P}$. A property ${\cal P}$ is called additive if for each graph $G$, all of whose components have the property $\cal P$, it follows that $G$ lies in ${\cal P}$ too. A property ${\cal P}$ is said to be hereditary if, whenever $G$ lies in ${\cal P}$, and $H$ is a subgraph of $G$, then $H$ also lies in ${\cal P}$.

Well-known additive and hereditary graph properties are for example (see [4]):

• ${\cal O}=\{G\in{\cal I}:E(G)=\emptyset\}$,

• ${\cal S}_{k}=\{G\in{\cal I}:\mbox{the maximum degree of $G$ is at most $k$}\}$,

• ${\cal O}_{k}=\{G\in{\cal I}:\mbox{each component of $G$ has order at most $k+1$}\}$,

• ${\cal W}_{k}=\{G\in{\cal I}:\mbox{the length of the longest path in $G$ is at most $k$}\}$,

• ${\cal D}_{k}=\{G\in{\cal I}:\mbox{ every subgraph of $G$ has minimum degree at most $k$}\}$.

Let ${\cal P}$ and ${\cal Q}$ denote additive hereditary graph properties. A $({\cal P},{\cal Q})$-total colouring of a simple graph $G$ is a colouring of the vertices and edges of $G$ such that for each colour $i$, the vertices coloured by $i$ induce a subgraph of $G$ with property ${\cal P}$, the edges coloured by $i$ induce a subgraph of $G$ with property ${\cal Q}$, and incident vertices and edges are coloured distinctly. The minimum number of colours needed such that a graph $G$ has a $({\cal P},{\cal Q})$-total colouring is called the (${\cal P},{\cal Q}$)-total chromatic number of $G$ and is denoted by $\chi^{\prime\prime}_{{\cal P},{\cal Q}}(G)$.

Early studies of total colourings of graphs occur in [2], [1] and [9]. In [5], the authors then generalised the idea of total colourings of graphs and describe such colourings in the context of additive hereditary graph properties. In particular, they found upper and lower bounds for the generalized total colourings of graphs with various additive hereditary properties.

In [3], they study generalised total colourings for families of planar graphs and give upper bounds for these chromatic numbers for proper colourings of the vertices while the monochromatic edge sets are allowed to be forests. Using the terminology and symbols introduced above, the total chromatic number $\chi^{\prime\prime}_{{\cal O},{\cal D}_{1}}(G)$ is studied for $G$ planar. In particular they show that if an even planar triangulation has a Hamilton cycle $H$ for which there is no cycle among the edges inside $H$, then such a graph needs at most four colours for a $({\cal O},{\cal D}_{1})$-total colouring as described above.

Furthermore, in [3], they conjecture that for all planar graphs $G$ one must have $\chi^{\prime\prime}_{{\cal D}_{1},{\cal D}_{1}}(G)\leq 4$. In this paper we define two classes of maximal planar graphs and show that for all graphs $G$ in these classes, $\chi^{\prime\prime}_{{\cal D}_{1},{\cal D}_{1}}(G)=4$. Therefore, we can confirm that for these two infinite classes of planar graphs the above-mentioned conjecture in [3] is true. We remark that, like in most results from [3], our graphs are hamiltonian.

2. Notation and basic results

A ${\cal D}_{1}$ vertex colouring of a graph $G$ is a colouring of the vertices of $G$ such that the subgraphs of $G$ induced by these colour classes are forests (i.e. lie in ${\cal D}_{1}$).

A planar graph $G$ is called maximal planar if the addition of any edge to $G$ results in a nonplanar graph.

The following lemma is a well-known characterisation of maximal planar graphs, found in [6] for example:

Lemma 2.1.

A planar graph $G$ with order $n\geq 3$ and size $m$ is maximal planar if and only if $m=3n-6$.

A maximal planar graph that contains a hamiltonian cycle will be called hamiltonian maximal planar.

We will construct a first class of maximal planar hamiltonian graphs.

Suppose that $n\geq 4$ is any integer. Let $G=(V(G),E(G))$ be the planar graph we obtain as follows:
Let $C_{n}$ denote a cycle on $n$ vertices; labelled $v_{1},\ldots,v_{n}$.
Add the following edges $v_{i}v_{j}$ to $C_{n}$ (on the inside of $C_{n}$):
where $i+j=n+2$ for all $2\leq i,j\leq n$ and
where $i+j=n+1$ for all $2\leq i,j\leq n$.
Finally, if $n>4$, then also add the edges $v_{1}v_{i}$ for all $3\leq i<n-1$ on the outside of the cycle. The class of all such graphs $G$ will be denoted by $\mathsf{MH}$. Our construction is illustrated in Figure 1.

Figure 1. The member of $\mathsf{MH}$ based on $C_{12}$.

Lemma 2.2.

Every graph in the class $\mathsf{MH}$ is maximal planar and hamiltonian.

Proof.

Let $G$ be any graph in $\mathsf{MH}$ with order $n\geq 4$. Then clearly $G$ is planar as well as Hamiltonian. From the construction above we obtain the size of $G$ in the case where $n$ is even and where $n$ is odd. First suppose that $n$ is odd, then to find the size of $G$ we add the $n$ cycle edges to the $\frac{n-3}{2}$ inside edges $v_{i}v_{j}$ (where $i+j=n+2$ and $2\leq i\leq n$) and to this we add the $\frac{n-3}{2}$ inside edges $v_{i}v_{j}$ (where $i+j=n+1$ and $2\leq i\leq n$) and then we add the $n-3$ outside edges $v_{1}v_{i}$ (where $3\leq i<n-1$). Therefore the size of $G$ is $n+\frac{n-3}{2}+\frac{n-3}{2}+n-3=3n-6$ and thus, by Lemma 2.1, it follows that $G$ is maximal planar.

Next suppose that $n$ is even, then adding the edges in the same order as above gives size $n+\frac{n-2}{2}+\frac{n-4}{2}+n-3=3n-6$ and so again, by Lemma 2.1, $G$ is maximal planar. ∎

3. Generalized total colouring in the class $\mathsf{MH}$

The main result in this section will show that for $G\in\mathsf{MH}$, we have $\chi^{\prime\prime}_{{\cal D}_{1},{\cal D}_{1}}(G)=4$. In order to prove this, we will need a few lemmas.

First, it will be useful to define the following sets. For all $k\in\{0,1,2\}$ let $S_{k}=\{x\in\mathbb{N}\mid x\bmod 3=k\}$.

Lemma 3.1.

Let $G$ be any graph in $\mathsf{MH}$ with vertex set $V(G)=\{v_{1},v_{2},\ldots,v_{n}\}$. Then the vertex colouring $c:V(G)\rightarrow\{1,2\}$ of $G$, defined as $c(v_{1})=1$ and for all $i\in S_{2}$ such that $2\leq i\leq\lceil\frac{n}{2}\rceil$, $c(v_{i})=c(v_{n-i})=1$ and otherwise $c(v_{i})=2$, is a ${\cal D}_{1}$ vertex colouring of $G$.

Proof.

Let $G$ be any graph in $\mathsf{MH}$ with vertex set $V(G)=\{v_{1},v_{2},\ldots,v_{n}\}$ and let $c$ be the colouring in the statement of the lemma. For $i=1,2$ we will use $\langle i\rangle$ to denote the set of all vertices $v$ in $V(G)$ such that $c(v)=i$.

By the construction of graphs in $\mathsf{MH}$ and by definition of $c$, we know that $v_{1}$ is a universal vertex in $G$ and we know that $c(v_{1})=1$. Furthermore, for all vertices $v_{i}$ and $v_{j}$ in $V(G)$ with $c(v_{i})=c(v_{j})=1$ (i.e $v_{i},v_{j}\in\langle 1\rangle$), if $i,j\neq 1$, then $v_{i}v_{j}\not\in E(G)$: since otherwise, if $v_{i}v_{j}$ is an edge in $G$, then, without loss of generality, $2\leq i\leq\lceil\frac{n}{2}\rceil$ and $i\in S_{2}$ while $j=n-k$ for some $k\in S_{2}$ such that $2\leq k\leq\lceil\frac{n}{2}\rceil$. However, then $i+j=(3l+2)+n-(3m+2)=3(l-m)+n$ for some integers $l$ and $m$, and by the construction of graphs in $\mathsf{MH}$, the edge $v_{i}v_{j}$ cannot exist. Therefore the subgraph of $G$ induced by the colour class $\langle 1\rangle$ is acyclic.

Furthermore, the subgraph of $G$ induced by $\langle 2\rangle$ is a path
$P_{1}:v_{n},v_{n-1},v_{3},v_{4},v_{n-3},v_{n-4},v_{6},v_{7},v_{n-6},v_{n-7},\ldots,v_{\lceil\frac{n}{2}\rceil}$ in the case where $n\bmod 6\in\{0,1,5\}$ and a path $P_{2}:v_{n},v_{n-1},v_{3},v_{4},v_{n-3},v_{n-4},v_{6},v_{7},v_{n-6},v_{n-7},\ldots,v_{\lceil\frac{n}{2}\rceil+1}$ in the case where $n\bmod 6\in\{2,3,4\}$. Therefore the subgraph induced by the colour class $\langle 2\rangle$ is also acyclic and thus the result holds. ∎

Figure 2. The vertex colouring and induced acyclic subgraphs in our example with $12$ vertices.

For every graph $G$ in $\mathsf{MH}$ with order $n\geq 4$, let $G_{n}$ denote the graph obtained from $G$ as follows:

1. Colour the vertices of $G$ with the colouring $c$ defined in Lemma 3.1.

2. Remove all edges from $G$ that join vertices with the same colour.

The graph $G_{12}$ obtained from our example of order $12$ is shown in Figure 3.

Figure 3. The subgraph $G_{12}$.

Note that the graph $G_{n}$ is planar and that every edge of $G_{n}$ lies on a cycle of length four. Furthermore, for all integers $n\geq 4$, the graph $G_{n}$ contains a vertex of degree 2, and in particular, deg${}_{G_{n}}(v_{n})=2$.

In the following lemma, let $G_{n}$ denote the graph constructed above, with vertex set $V(G)=\{v_{1},v_{2},\ldots,v_{n}\}$, numbered as in the construction above.

Lemma 3.2.

For all positive integers $n\geq 5$, if $H$ and $G$ are graphs in $\mathsf{MH}$ with vertex sets $V(H)=\{u_{1},u_{2},\ldots,u_{n-1}\}$ and $V(G)=\{v_{1},v_{2},\ldots,v_{n}\}$ respectively, then the graph $H_{n-1}$ is isomorphic to $G_{n}-v_{\lceil\frac{n+1}{2}\rceil}$ if $n$ is even, and isomorphic to $G_{n}-v_{\lceil\frac{n}{2}\rceil}$ if $n$ is odd. In both cases the removed vertex has degree $2$ in $G_{n}$.

Proof.

Take any integer $n\geq 5$ and let the graph $H_{n-1}$ be one that is constructed from a graph $H$ in $\mathsf{MH}$, with order $n-1$ and $V(H)=\{u_{1},u_{2},\ldots,u_{n-1}\}$. By Lemma 2.2, $H$ is a triangulation and we may choose an embedding in the plane such that the vertices $u_{1},u_{\lceil\frac{n-1}{2}\rceil}$ and $u_{\lceil\frac{n-1}{2}\rceil+1}$ lie on the outer face of $H$. Note that any graph $G$ in $\mathsf{MH}$ (up to isomorphism) with order $n$, can be obtained from $H$ by joining a single vertex $v$ with the vertices $u_{1},u_{\lceil\frac{n-1}{2}\rceil}$ and $u_{\lceil\frac{n-1}{2}\rceil+1}$ in $H$. One can then easily see the correspondence between the vertices $V(G)=\{v_{1},v_{2},\ldots,v_{n}\}$ used in the construction of $G$ and the vertices $\{u_{1},u_{2},\ldots,u_{\lceil\frac{n-1}{2}\rceil},v,u_{\lceil\frac{n-1}{2}\rceil+1},\ldots,u_{n-1}\}=V(H)\cup\{v\}$.

Furthermore, if we colour the vertices of $G$ with the colouring $c$ defined in Lemma 3.1, then since this colouring is acyclic and $v_{\lceil\frac{n-1}{2}\rceil}v_{\lceil\frac{n-1}{2}\rceil+2}$ is an edge in $G$ (corresponding to the edge $u_{\lceil\frac{n-1}{2}\rceil}u_{\lceil\frac{n-1}{2}\rceil+1}$ in $H$), that forms a cycle of length $3$ together with the vertex $v_{1}$ which has colour $1$, at least one of the vertices $v_{\lceil\frac{n-1}{2}\rceil}$ and $v_{\lceil\frac{n-1}{2}\rceil+2}$ must have colour $2$. As the colouring is acyclic, the case $c(v_{\lceil\frac{n-1}{2}\rceil})=c(v_{\lceil\frac{n-1}{2}\rceil+2})=2$ will yield $c(v_{\lceil\frac{n-1}{2}\rceil+1})=1$, implying that the degree of $v_{\lceil\frac{n-1}{2}\rceil+1}$ will be $2$ in $G_{n}$. In the case that $v_{\lceil\frac{n-1}{2}\rceil}$ and $v_{\lceil\frac{n-1}{2}\rceil+2}$ have different colours, the cycle consisting of $v_{1}$, $v_{\lceil\frac{n-1}{2}\rceil+1}$ and the vertex of colour $1$ in $\{v_{\lceil\frac{n-1}{2}\rceil},v_{\lceil\frac{n-1}{2}\rceil+2}\}$ will yield colour $2$ for $v_{\lceil\frac{n-1}{2}\rceil+1}$, showing again that the degree of $v_{\lceil\frac{n-1}{2}\rceil+1}$ is $2$ in $G_{n}$.

Now, if $v_{\lceil\frac{n-1}{2}\rceil+1}$ is removed from the graph $G_{n}$, then the only edges lost, come from the set $\{v_{\lceil\frac{n-1}{2}\rceil}v_{\lceil\frac{n-1}{2}\rceil+1},v_{\lceil\frac{n-1}{2}\rceil+1}v_{\lceil\frac{n-1}{2}\rceil+2},v_{1}v_{\lceil\frac{n-1}{2}\rceil+1}\}$ and the remaining graph is isomorphic to $H_{n-1}$, as the colouring of $H$ is consistent with the colouring of $G$ constructed from $H$ by adding the vertex $v$.

To end the proof we remark that if $n$ is even we have $\lceil\frac{n-1}{2}\rceil+1=\lceil\frac{n}{2}\rceil+1$ and that if $n$ is odd we have $\lceil\frac{n-1}{2}\rceil+1=\lceil\frac{n}{2}\rceil$. So the vertex $v_{\lceil\frac{n-1}{2}\rceil+1}$ that we remove from $G_{n}$ is indeed equal to either $v_{\lceil\frac{n}{2}\rceil+1}$ or $v_{\lceil\frac{n}{2}\rceil}$, depending on the parity of $n$. ∎

Lemma 3.3.

Let $n\geq 4$ be any positive integer and $G$ be any graph in $\mathsf{MH}$ with vertex set $V(G)=\{v_{1},v_{2},\ldots,v_{n}\}$. Then the edge set of the graph $G_{n}$ can be decomposed into two sets $F_{1}$ and $F_{2}$ such that the graphs induced by each of these sets lie in ${\cal D}_{1}$.

Proof.

Let $G_{n}$ be the graph constructed from $G$ with vertex set $V(G_{n})=V(G)=\{v_{1},v_{2},\ldots,v_{n}\}$. From Lemma 3.2, there exists a vertex $v\in V(G_{n})$ such that deg$(v)=2$, in particular, if $n$ is odd, then one can take $v=v_{\lceil\frac{n}{2}\rceil}$ and if $n$ is even, then $v=v_{\lceil\frac{n+1}{2}\rceil}$ has degree $2$. To decompose the edges of $G_{n}$ as required, we consider two copies $F_{1}$ and $F_{2}$ of the empty graph $nK_{1}$, with the vertices of each labelled as in $G_{n}$. Consider the graph $G_{n}$. We now apply the following algorithm:

Place one of the two edges incident with $v$ (in $G_{n}$), between the corresponding vertices in $F_{1}$ and the other edge between the corresponding vertices in $F_{2}$.
Remove the vertex $v$ from $G_{n}$. Note that, by Lemma 3.2, the resulting graph $G_{n}-v$ is isomorphic to a graph $G_{n-1}$ where $G_{n-1}$ contains a vertex $u$ such that deg$(u)=2$.
Continue with the above algorithm until the resulting graph is isomorphic to a cycle $G_{4}\cong C_{4}$ of length four.
Let $x$ denote any vertex in $G_{4}$. Place one of the two edges incident with $x$ (in $G_{4}$) between the corresponding vertices in $F_{1}$ and the other edge between the corresponding vertices in $F_{2}$.
Remove $x$ from $G_{4}$.
Finally place one of the two remaining edges in the resulting $G_{2}$ $(\cong P_{3})$ between the corresponding vertices in $F_{1}$ and the other edge between the corresponding vertices in $F_{2}$.

By the construction of $F_{1}$ and $F_{2}$ above it is easy to see that the graphs induced by both $F_{1}$ and $F_{2}$ are acyclic, since once the edge incident with a particular vertex $v$, in some graph $G_{i}$ ($2\leq i\leq n$), such that deg$(v)=2$, is added to $F_{j}$, ($j\in\{1,2\}$), the vertex $v$ is never again encountered in $F_{j}$ as it is deleted from $G_{i}$.

Using the above, we are able to decompose the edge set of $G_{n}$ into two sets such that the graph induced by edges in $F_{1}$ and the graph induced by edges in $F_{2}$ both lie in ${\cal D}_{1}$. ∎

Figure 4. The decomposition of $G_{12}$ into two forests.

Theorem 3.4.

For all integers $n\geq 4$, every graph $G$ in $\mathsf{MH}$ with order $n$ satisfies $\chi^{\prime\prime}_{{\cal D}_{1},{\cal D}_{1}}(G)=4$.

Proof.

Let $G$ be any graph in $\mathsf{MH}$ with order $n\geq 4$ and vertex set $V(G)=\{v_{1},v_{2},\ldots,v_{n}\}$. Colour the vertices of $G$ with the colouring $c:V(G)\rightarrow\{1,2\}$ of $V(G)$ such that $c(v_{1})=1$ and for all $i\in S_{2}$ such that $2\leq i\leq\lceil\frac{n}{2}\rceil$, $c(v_{i})=c(v_{n-i})=1$ and otherwise $c(v_{i})=2$. By Lemma 3.1, the subgraphs induced by the two colour classes $\langle 1\rangle$ and $\langle 2\rangle$ of $c$ are acyclic. Consider the subgraph $G_{n}$ of $G$. Applying the method used in the proof of Lemma 3.3, colour the edges of $G_{n}$ induced by $F_{1}$ with colour 3 and the edges induced by $F_{2}$ with colour 4. Finally, for all edges $v_{i}v_{j}\in G$ such that $v_{i}v_{j}\not\in G_{n}$, ($1\leq i,j\leq n$) if $c(v_{i})=c(v_{j})=1$, then colour the edge $v_{i}v_{j}$ with colour 2, and for all edges $v_{i}v_{j}\in G$ such that $v_{i}v_{j}\not\in G_{n}$, ($1\leq i,j\leq n$) if $c(v_{i})=c(v_{j})=2$, colour the edge $v_{i}v_{j}$ with colour 1.

The total colouring above provides a ${\cal D}_{1}$ colouring of the vertices of $G$ as well as a ${\cal D}_{1}$ colouring of the edges of $G$ such that incident vertices and edges receive distinct colours and therefore
$\chi^{\prime\prime}_{{\cal D}_{1},{\cal D}_{1}}(G)\leq 4$.

Furthermore, the complete graph $K_{4}$ is the smallest graph in $\mathsf{MH}$ and clearly $K_{4}$ is a subgraph of all graphs in $\mathsf{MH}$. However, if we try to find a total colouring of $K_{4}$, then we see that, firstly, we need at least two colours for the vertices and since $K_{4}$ is a triangulation, at most two vertices may have the same colour. Thus if we use exactly two colours for the vertices, then there are two vertices of each colour. However, then since $K_{4}$ is complete, we can always find a 4-cycle $C:u_{1},u_{2},u_{3},u_{4},u_{1}$ in the graph with vertices of alternating colours. However, then none of the edges between the vertices on $C$ may receive colour 1 or 2. Furthermore, since $C$ is a cycle, we will need an additional two colours to colour its edges. However, if we use three colours for the vertices of $K_{4}$, then two vertices must have the same colour, say 1. Call the other two vertices $u$ and $v$ and call their colours $2$ and $3$ respectively. Then the only edge that may be coloured with $1$ is $uv$. Now the remaining five edges are the following: the edge between the two vertices of colour $1$, two vertices between $u$ and the vertices with colour $1$ and two between $v$ and the vertices with colour $1$. They form two cycles of length $3$ sharing the edge between the vertices of colour $1$. Trying to use only $3$ colours, the edges on $u$ must be coloured with colour $3$ and the ones on $v$ with colour $2$. For the edge between the two vertices of colour $1$ either of the colours $2$ or $3$ will yield a monochromatic cycle of length $3$ so we will need a fourth colour. Therefore $\chi^{\prime\prime}_{{\cal D}_{1},{\cal D}_{1}}(K_{4})\geq 4$. Since $K_{4}$ is a subgraph of every graph in $\mathsf{MH}$, it follows that $\chi^{\prime\prime}_{{\cal D}_{1},{\cal D}_{1}}(G)=4$. ∎

The following corollary to Theorem 3.4 follows from [5], since for a positive integer $k$, a subgraph $H$ of a graph $G$ and additive hereditary properties ${\cal P}$ and ${\cal Q}$, if $\chi^{\prime\prime}_{{\cal P},{\cal Q}}(G)\leq k$, then $\chi^{\prime\prime}_{{\cal P},{\cal Q}}(H)\leq k$.

Corollary 3.5.

Every (planar) subgraph of a graph $G$ in $\mathsf{MH}$ satisfies
$\chi^{\prime\prime}_{{\cal D}_{1},{\cal D}_{1}}(G)\leq 4$.

4. Generalized total colourings for triangulated square grids

We now construct another family of hamiltonian maximal planar graphs.

Let $k\geq 2$ and $l\geq 2$ denote positive integers and $P_{k}$ and $P_{l}$ denote paths of order $k$ and $l$, respectively. The cartesian product of $P_{k}$ and $P_{l}$ is called a $k\times l$ grid or a $k\times l$ lattice graph and has order $kl$.

Let $G$ be a $n\times n$ grid for some positive integer $n\geq 3$ and let $V(G)$ denote the vertex set of $G$. To label the vertices of a square grid $G$, we will use notation similar to that used for entries of a matrix. Thus $v_{ij}$ will denote the vertex in row $i$ and column $j$ of our grid. We will define a triangulated grid of $G$ to be the graph $Gt$ obtained from $G$ by adding a diagonal edge from the top right corner to the bottom left corner of every induced subgraph $H$ of $G$ such that $H$ is isomorphic to a cycle of length four, and we will add an edge between the vertex $v_{11}$ and every vertex on the outer face of $V(G)$.

More formally, if $V(G)=\{v_{11},v_{12},\ldots,v_{nn}\}$, then $Gt$ is the graph obtained by adding all edges $v_{ij}v_{(i+1)(j-1)}$ (for all $1\leq i,j\leq n$) and all edges $v_{11}v_{1j}$, $v_{11}v_{i1}$, $v_{11}v_{nj}$ and $v_{11}v_{in}$ for all $1\leq i\leq n-1$ and $2\leq j\leq n$ to $G$. It is easy to see that the graph $Gt$ is planar. Furthermore, the graph $Gt$ is maximal planar, since it has order $n^{2}$ and size $2(n-1)n+(n-1)^{2}+(4n-4-3)=3n^{2}-6$ (adding edges on the grid $G$ to the diagonal edges and adding this to the order of the neighbourhood of $v_{11}$ without the edges $v_{12}$ and $v_{21}$).

Figure 5. The triangulated $4\times 4$ grid.

Theorem 4.1.

Let $G$ be a $n\times n$ grid for any integer $n\geq 3$. Then the triangulated grid $Gt$ satisfies, $\chi^{\prime\prime}_{{\cal D}_{1},{\cal D}_{1}}(Gt)=4$.

Proof.

First we will show that $\chi^{\prime\prime}_{{\cal D}_{1},{\cal D}_{1}}(Gt)\leq 4$. Similar to the proof of Theorem 3.4, in order to show this upper bound, we will first define a vertex colouring of a graph $Gt$ that will use two colours and we will show that the graphs induced by the two colour classes are both acyclic. Then we will show that the graph $H$ resulting from $Gt$ by removing all edges whose end vertices lie in the same colour class can be edge-partitioned into two spanning forests $F_{1}$ and $F_{2}$. From this we will be able to provide the necessary total colouring.

Take any graph isomorphic to a triangulated grid $Gt$.

Consider the vertex colouring $c:V(Gt)\rightarrow\{1,2\}$ defined by

$c(v_{ij})=\left\{\begin{array}[]{ll}1&\mbox{ if }1\leq i\leq j\mbox{ and }i+j\mbox{ is even, or}\\ &\mbox{ if }1\leq j\leq i-3,i\geq 4\mbox{ and }i+j\mbox{ is odd, and }\\ 2&\mbox{ otherwise. }\end{array}\right.$

Let $\langle 1\rangle$ and $\langle 2\rangle$ denote the colour classes of $c$, then the graph induced by the vertices in $V(Gt)$ that lie in $\langle 1\rangle$, is acyclic and the same holds for the graph induced by the vertices that lie in $\langle 2\rangle$: this is easily seen, since by definitions of the edge set $E(Gt)$ of $Gt$ and the colouring $c$, the graph (say $G_{2}$) induced on the vertices in $\langle 2\rangle$ is a generalized caterpillar with, as spine, the path $v_{12},v_{21},v_{31},\ldots,v_{(n-1)n}$ of length $2n-2$ and legs of varying lengths $k$ such that $0\leq k\leq\lceil\frac{n}{2}\rceil$. Furthermore, the graph (say $G_{1}$) induced on the vertices of $\langle 1\rangle$ is a generalized star with center $v_{11}$ and with $2n-4$ arms of varying lengths $k$ such that $1\leq k\leq\lceil\frac{n}{2}\rceil$.

Now let $H$ denote the spanning subgraph of $Gt$ that results when we remove the edge sets of $G_{1}$ and $G_{2}$ from $Gt$.

Let $F_{1}$ denote the subgraph of $H$ induced by the edges $\{v_{ij}v_{kl}\in E(H)\ |\ i=k-1,j=l,c(v_{ij})=1\mbox{ and }c(v_{kl})=2\}\cup\{v_{ij}v_{kl}\in E(H)\ |\ i=k,j=l-1,c(v_{ij})=1\mbox{ and }c(v_{kl})=2\}\cup\{v_{ij}v_{kl}\in E(H)\ |\ i=k-1,j=l+1,c(v_{ij})=1\mbox{ and }c(v_{kl})=2\}\cup\{v_{11}v_{kl}\in E(H)\ |\ k=1\mbox{ and }c(v_{kl})=2,\mbox{ or }l=n\mbox{ and }c(v_{kl})=2\}$. It is easily seen that $F_{1}$ is a forest (a generalized star with $v_{11}$ its central vertex and with $n$ arms, such that every arm is a tree).

Let $F_{2}$ denote the subgraph of $H$ induced by the edges $\{v_{ij}v_{kl}\in E(H)\ |\ i=k-1,j=l,c(v_{ij})=2\mbox{ and }c(v_{kl})=1\}\cup\{v_{ij}v_{kl}\in E(H)\ |\ i=k,j=l-1,c(v_{ij})=2\mbox{ and }c(v_{kl})=1\}\cup\{v_{ij}v_{kl}\in E(H)\ |\ i=k-1,j=l+1,c(v_{ij})=2\mbox{ and }c(v_{kl})=1\}\cup\{v_{11}v_{kl}\in E(H)\ |\ l=1\mbox{ and }c(v_{kl})=2,\mbox{ or }k=n\mbox{ and }c(v_{kl})=2\}$. It is easily seen that $F_{2}$ is a forest (the union of a generalized star with $n-1$ arms (such that the arms are paths) together with a union of paths).

Therefore, to show that $\chi^{\prime\prime}_{{\cal D}_{1},{\cal D}_{1}}(Gt)\leq 4$, we start with a graph $Gt$ and we colour its vertices with the colouring $c$ defined above to obtain two colour classes $\langle 1\rangle$ and $\langle 2\rangle$. To the edges of $Gt$, first we colour the edges of the graph $G_{1}$ (defined above) with the colour 2 and we colour the edges of the graph $G_{2}$ with the colour 1. Next we colour the edges of the forest $F_{1}$ with a new colour 3 and finally the edges of the forest $F_{2}$ with a new colour 4. From our observations above, we have that the subgraphs induced by vertices with the same colour lie in ${\cal D}_{1}$, all incident vertices and edges have distinct colours and the graphs induced by edges with the same colour lie in ${\cal D}_{1}$. Thus we may conclude that $\chi^{\prime\prime}_{{\cal D}_{1},{\cal D}_{1}}(Gt)\leq 4$.

Now we will show that $\chi^{\prime\prime}_{{\cal D}_{1},{\cal D}_{1}}(Gt)\geq 4$. Note that the induced subgraph $\langle v_{11},v_{1(n-1)},v_{1n},v_{2(n-1)},v_{2n}\rangle$ of any triangulated grid $G_{t}$ is isomorphic to a wheel, which we will denote by $W$, which has order 5 and central vertex $v_{1n}$. We will show that $\chi^{\prime\prime}_{{\cal D}_{1},{\cal D}_{1}}(W)\geq 4$, and therefore assume (to the contrary) that $\chi^{\prime\prime}_{{\cal D}_{1},{\cal D}_{1}}(W)\leq 3$. Since $W$ contains cycles, we need at least two colours with which to colour the vertex set of $W$. For the sake of simplicity, let’s label the vertices of $W$ as $\{u_{1},u_{2},u_{3},u_{4},x\}$, where $x$ denotes the central vertex of $W$. We begin by colouring the vertices in $W$ that lie on the outer 4-cycle (which we will denote by $C$), i.e., all vertices excepting the vertex $x$. Consider the total colouring $c:\{u_{1},u_{2},u_{3},u_{4},x\}\cup E(W)\rightarrow\{1,2,3\}$ of $V(W)\cup E(W)$.
Case 1: Suppose that $c(u_{1})=c(u_{3})\neq c(u_{2})=c(u_{4})$. Then, since incident vertices and edges must receive distinct colours and $C$ is a cycle, we will need two new colours to colour $E(C)$. Therefore $4\leq\chi^{\prime\prime}_{{\cal D}_{1},{\cal D}_{1}}(C)\leq\chi^{\prime\prime}_{{\cal D}_{1},{\cal D}_{1}}(W)\leq 3$ — a contradiction.
Case 2: Suppose now that $c(u_{1})=c(u_{4})\neq c(u_{2})=c(u_{3})$ and, without loss of generality, $c(u_{1})=1$ and $c(u_{2})=2$. Then, in $W$, the vertex $x$ must satisfy $c(x)=3$. In order to satisfy the restrictions imposed by the total colouring, we know that $c(u_{1}x)=c(u_{4}x)=2$ and $c(u_{2}x)=c(u_{3}x)=1$. However, then $c(u_{1}u_{4})=3$ and thus the only available colour assignment for $u_{2}u_{3}$ is $c(u_{2}u_{3})=3$ — now all the edges of $C$ are coloured the same, a contradiction.
Case 3: Finally, suppose that $c(u_{1})=c(u_{2})=c(u_{3})\neq c(u_{4})$ and (without loss of generality) that $c(u_{1})=1$ and $c(u_{4})=2$. Clearly, $c(x)\neq 1$.
If $c(x)=2$, then $c(u_{1}x)=c(u_{3}x)=c(u_{3}u_{4})=c(u_{1}u_{4})=3$ and thus the colour class $\langle 3\rangle$ induces a cycle $u_{1},x,u_{3},u_{4}$ — a contradiction. Thus $c(x)=3$. However, this forces $c(u_{1}u_{4})=c(u_{3}u_{4})=3$ and $c(u_{2}x)=c(u_{3}x)=2$ and the latter colouring forces $c(u_{2}u_{3})=3$. This makes it impossible for us to colour the edge $u_{1}u_{2}$ with one of the three colours since $c(u_{1}u_{2})\neq 1$ as $c(u_{1})=c(u_{2})=1$; also $c(u_{1}u_{2})=3$ causes $\langle 3\rangle$ to induce a cycle isomorpic to $C$ and finally $c(u_{1}u_{2})=2$ results in a triangle $u_{1},u_{2},x$ induced by $\langle 2\rangle$.
Therefore $\chi^{\prime\prime}_{{\cal D}_{1},{\cal D}_{1}}(W)\geq 4$. Since every triangulated square grid $Gt$ contains the wheel $W$, we may conclude that $\chi^{\prime\prime}_{{\cal D}_{1},{\cal D}_{1}}(Gt)\geq 4$ from which the result follows. ∎

Figure 6. The vertex colouring and induced acyclic subgraphs in the triangulated $4\times 4$ grid.

Figure 7. The decomposition of the triangulated $4\times 4$ grid into two forests.

Corollary 4.2.

Let $G$ be a $n\times n$ grid for any integer $n\geq 3$ and let $Gt$ denote the triangulated grid of $G$. Then every (planar) subgraph of $Gt$ satisfies $\chi^{\prime\prime}_{{\cal D}_{1},{\cal D}_{1}}(Gt)\leq 4$.