Graceful coloring is computationally hard

Abstract

Given a (proper) vertex coloring $f$ of a graph $G$, say $f\colon V(G)\to\mathbb{N}$, the difference edge labelling induced by $f$ is a function $h\colon E(G)\to\mathbb{N}$ defined as $h(uv)=|f(u)-f(v)|$ for every edge $uv$ of $G$. A graceful coloring of $G$ is a vertex coloring $f$ of $G$ such that the difference edge labelling $h$ induced by $f$ is a (proper) edge coloring of $G$. A graceful coloring with range $\{1,2,\dots,k\}$ is called a graceful $k$-coloring. The least integer $k$ such that $G$ admits a graceful $k$-coloring is called the graceful chromatic number of $G$, denoted by $\chi_{g}(G)$.

We prove that $\chi(G^{2})\leq\chi_{g}(G)\leq a(\chi(G^{2}))$ for every graph $G$, where $a(n)$ denotes the $n$th term of the integer sequence A065825 in OEIS. We also prove that graceful coloring problem is NP-hard for planar bipartite graphs, regular graphs and 2-degenerate graphs. In particular, we show that for each $k\geq 5$, it is NP-complete to check whether a planar bipartite graph of maximum degree $k-2$ is graceful $k$-colorable. The complexity of checking whether a planar graph is graceful 4-colorable remains open.

1 Introduction

Many branches of mathematics started out as problems in recreational mathematics which are easy to understand, yet challenging to solve. The story of graph theory is no different. The innocuous problem of coloring maps using only 4 colors gave birth to a thriving area of graph theory named graph coloring. The notion of graph labelling is a generalisation of graph coloring. Graph labelling is an area of immense theoretical interest and diverse practical applications, evident from Gallian’s dynamic survey [gallian]. Similar to how attempts to prove the four color conjecture lead to the historical origin or popularity of the area of graph colorings, study of graceful labelling and harmonious labelling lead to the boom of the area of graph labellings [gallian].

The definition of graceful labelling requires the notion of difference edge labelling induced by a vertex labelling. Given a vertex labelling $f$ of a graph $G$, say $f\colon V(G)\to\mathbb{N}$, the difference edge labelling induced by $f$ is a function $h\colon E(G)\to\mathbb{N}\cup\{0\}$ defined as $h(uv)=|f(u)-f(v)|$ for every edge $uv$ of $G$. A graceful labelling of a graph $G$ on $m$ edges is an injection $f\colon V(G)\to\{0,1,\dots,m\}$ such that the difference edge labelling $h$ induced by $f$ is an injection from $E(G)$ to $\{1,2,\dots,m\}$ [gallian].

The most popular problem on graceful labelling is settling the infamous Kötzig-Ringel-Rosa conjecture, better known as the graceful tree conjecture, which states that all trees are graceful. The graceful tree conjecture is far from resolved till date. Hence, the practical approaches to the problem includes resolving the conjecture for subclasses of trees on one hand, and resolving weaker versions of the conjecture on the other hand. One way to produce notions weaker than graceful labelling is to impose restrictions locally on vertex neighbourhoods rather than globally. This produces the notion of graceful coloring. A vertex labelling $f$ of a graph $G$, say $f\colon V(G)\to\mathbb{N}$, is a graceful coloring of $G$ if (i) $f$ is an injection when limited to each vertex neighbourhood, and (ii) the induced difference edge labelling $h$ is an injection when limited to each vertex neighbourhood; formally, the restriction $f_{\restriction N[v]}$ is an injection and $h_{\restriction G[N[v]]}$ is an injection for the closed neighbourhood $N[v]$ of each vertex $v$ in $G$. In other words, a graceful coloring of $G$ is a (proper vertex) coloring $f$ of $G$ such that the difference edge labelling $h$ induced by $f$ is a (proper) edge coloring of $G$ [bi_byers] (see Figure 1 for an example). The graceful coloring first appeared in Bi et al. [bi_byers], and was studied in more detail in Byers’ thesis [byers].

Figure 1: A graceful coloring of a graph. This is a graceful 5-coloring.

For $k\in\mathbb{N}$, a graceful $k$-coloring of $G$ is a graceful coloring of $G$ with range $\{1,2,\dots,k\}$ (i.e., $f\colon V(G)\to\{1,2,\dots,k\}$). The least integer $k$ such that $G$ admits a graceful $k$-coloring is called the graceful chromatic number of $G$, denoted by $\chi_{g}(G)$.

It is easy to observe that under a graceful coloring, no two neighbours of a vertex can get the same color. A (proper) coloring of a graph $G$ with this property is called a distance-two coloring. Hence, every graceful coloring is a distance-two coloring, but the converse is not true. The least number of colors required to produce a distance-two coloring of a graph $G$ is called the distance-two chromatic number of $G$, and is equivalent to the chromatic number of the square graph $G^{2}$. We denote the distance-two chromatic number of $G$ by $\chi(G^{2})$. Obviously, $\chi(G^{2})\leq\chi_{g}(G)$.

We relate the graceful chromatic number of complete graphs to integer sequences. Throughout this paper, $a(n)$ denotes the $n$th term of the integer sequence A065825 in OEIS [a065825-oeis]. It is known that $\chi_{g}(K_{n})=a(n)$ [laavanya_deviYamini].

In this paper, we prove that $\chi(G^{2})\leq\chi_{g}(G)\leq a(\chi(G^{2}))$ for every graph $G$. In addition, we prove that graceful coloring problem is NP-hard for planar bipartite graphs, regular graphs and 2-degenerate graphs. We show that (i) for each $k\geq 6$, it is NP-complete to check whether a planar bipartite 3-degenerate graph of maximum degree $k-2$ is graceful $k$-colorable, (ii) it is NP-complete to check whether a 3-regular 3-connected planar bipartite graph is graceful 5-colorable, and (iii) it is NP-complete to check whether a 2-degenerate graph of maximum degree 3 is graceful 4-colorable. The complexity of checking whether a planar graph is graceful 4-colorable remains open.

For brevity, we present overviews in the paper, and relegate details to the extended version of the paper.

2 Results

2.1 Graceful Coloring and Integer Sequences

By definition, $a(n)$ is the least integer $k$ for which $\{1,2,\dots,k\}$ contains a subset $S$ of cardinality $n$ such that no three distinct elements $i,j,k$ of $S$ satisfy $|i-j|=|j-k|$. This imply the following.

Theorem 1 ([laavanya_deviYamini]).

$\chi_{g}(K_{n})=a(n)$ for every positive integer $n$. ∎

If $f$ is a distance-two $q$-coloring of a graph $G$ and $h$ is a graceful coloring of the complete graph $K_{q}$ with vertex set $\{1,2,\dots,q\}$, then $h\circ f$ is a graceful coloring of $G$. Thus, we have the following theorem.

Theorem 2.

$\chi(G^{2})\leq\chi_{g}(G)\leq a(\chi(G^{2}))$ for every graph $G$. ∎

2.2 Complexity of Graceful Coloring

The problem Graceful $k$-Colorability is defined as follows.

Graceful $k$-Colorability
Instance: A graph $G$.
Question: Does $G$ admit a graceful $k$-coloring?

First, we show that Graceful $k$-colorablity of planar graphs is NP-complete for all $k\geq 5$. As a prelude to the reduction, we point out the following.

Theorem 3.

Let $k\geq 5$, and let $G$ be a graph with minimum degree $\delta(G)\geq k-2$. Then, $G$ is graceful $k$-colorable if and only if $G$ is distance-two 4-colorable. ∎

Construction 1.

Parameter: An integer $k\geq 5$ (not part of input).
Input: A 3-regular graph $G$.
Output: A graph $G^{\prime}$ of maximum degree $k-2$.
Guarantee: $G^{\prime}$ is graceful $k$-colorable if and only if $G$ is distance-two 4-colorable.
Steps: Introduce a copy of $G$. Attach $k-5$ leaf vertices at each vertex of the copy of $G$.

Proof of Guarantee (overview).

Suppose that $G^{\prime}$ is graceful $k$-colorable. That is, $G^{\prime}$ admits a graceful $k$-coloring $f^{\prime}\colon V(G^{\prime})\to\{1,2,\dots,k\}$. If $v$ is a vertex of $G^{\prime}$ colored 3 by $f^{\prime}$, then $v$ has at most $k-3$ neighbours in $G^{\prime}$. As a result, no non-leaf vertex $v$ of $G^{\prime}$ can get color 3 (because $d_{G^{\prime}}(v)=k-2$). Similarly, each non-leaf vertex $v$ of $G^{\prime}$ cannot get any of the colors $4,5,\dots,k-2$, and thus $v$ can get only the colors $1,2,k-1$ or $k$ under $f$. Hence, the restriction of $f$ to $V(G)$ is a graceful coloring and in particular a distance-two coloring of $G$ that uses only 4 colors (namely, $1,2,k-1$ and $k$). Therefore, $G$ is distance-two 4-colorable.

Conversely, suppose that $G$ is distance-two 4-colorable. Then, there exists a distance-two 4-coloring $f$ of $G$ with color paletter $\{1,2,k-1,k\}$ (i.e., $f\colon V(G)\to\{1,2,k-1,k\}$). We show that $f$ can be extended into a graceful $k$-coloring $f^{\prime}$ of $G^{\prime}$. For each non-leaf vertex $v$ of $G^{\prime}$, define $f^{\prime}(v)=f(v)$, and color the leaf neighbours of $v$ in $G^{\prime}$ as follows: if $f^{\prime}(v)=2$, then color the leaf neighbours of $v$ with colors $\{4,5,\dots,k-2\}$ in a bijective fashion; if $f^{\prime}(v)=k-1$, then color the leaf neighbours of $v$ with colors $\{3,4,\dots,k-3\}$ in a bijective fashion; if $f^{\prime}(v)\in\{1,k\}$, then color the leaf neighbours of $v$ with distinct colors from $\{3,4,\dots,k-2\}$. We complete the proof by showing that $f^{\prime}$ is a graceful $k$-coloring of $G^{\prime}$. ∎

Observe that for $k=5$, the output graph in Construction 1 is the same as the input graph (i.e., $G^{\prime}=G$). Moreover, the construction obviously takes only time polynomial in the input size. Also, observe that Construction 1 preserves planarity and bipartiteness. Further, Feder, Hell and Subi [feder] proved that it is NP-complete to check whether a 3-regular 3-connected planar bipartite graph is distance-two 4-colorable. Thanks to Construction 1, this imply the following.

Theorem 4.

Graceful 5-colorablity is NP-complete for 3-regular 3-connected planar bipartite graphs. ∎

Theorem 5.

For $k\geq 6$, Graceful $k$-colorablity is NP-complete for planar bipartite graphs of maximum degree $k-2$. ∎

Next, we show that Graceful 4-colorablity is NP-complete by reducing from the following problem.

Positive Not-All-Equal $3$-Sat E4
Instance: A set $X$ of variables and a set $C$ of clauses over $X$ are specified, where each clause $c\in C$ consists of three distinct variables, and each variable appears in exactly four clauses (the formula contains no negations).
Question: Does there exist a truth assignment for $X$ such that each clause contains at least one true and at least one false literal?

Darmann and Döcker [darmann_docker] demonstrated the NP-Completeness of this problem.

Theorem 6.

Graceful 4-colorablity is NP-complete for the class of 2-degenerate graphs of maximum degree 3.

Proof overview.

Given a boolean formula $\mathcal{F}=(X,C)$ which is an instance of Positive Not-All-Equal $3$-Sat E4, we construct a graph $G$ by taking the variable-clause incidence graph $G_{\mathcal{F}}$ of the formula $\mathcal{F}$, and then replacing each variable vertex $x_{j}$ and incident edges by the variable gadget $G^{X}$ (see Figure 2) and replacing each clause vertex $c_{i}$ and incident edges by the clause gadget $G^{C}$ (see Figure 3).

Figure 2: Variable gadget $G^{X}$. Vertex $x_{j}$ together with incident edges are replaced by this gadget, and the edges $e_{1},e_{2},e_{3}$ and $e_{4}$ incident on $x_{j}$ in $G_{\mathcal{F}}$ become the dashed edges of the gadget in $G$.

Figure 3: Clause gadget $G^{C}$. Vertex $c_{i}$ together with incident edges are replaced by this gadget, and the edges $e_{1},e_{2}$ and $e_{3}$ incident on $c_{i}$ in $G_{\mathcal{F}}$ become the dashed edges of the gadget in $G$.

We observe that for every graceful 4-coloring $f$ of $G$,
(i) $f(c_{1i}),f(c_{2i}),f(c_{3i})\in\{1,4\}$ and not all equal for each $i$, and
(ii) $f(x_{lj})=f(x_{kj})=f(x_{mj})=f(x_{nj})\in\{1,4\}$ for all $j$.
Using these properties, we show that $\mathcal{F}$ is a yes instance of Positive Not-All-Equal $3$-Sat E4 whenever $G$ admits a graceful 4-coloring $f$. In the other direction, we show that if $\mathcal{F}$ is a yes instance of Positive Not-All-Equal $3$-Sat E4, then a graceful 4-coloring of $G$ can be obtained using the colorings schemes shown in Figure 4 and Figure 5. Consider a truth assignment $\mathcal{A}$ for the formula $\mathcal{F}$ such that each clause contains a true variable and a false variable. If a variable $x_{j}$ is true under $\mathcal{A}$, then color the corresponding variable gadget $G^{X}$ by the coloring $h$ shown in Figure 4. If a variable $x_{j}$ is false under $\mathcal{A}$, then color the corresponding variable gadget $G^{X}$ using the ‘opposite’ colors of that shown in Figure 4 (i.e., color each vertex $v$ in the gadget using the color $5-h(v)$). This can be extended to a graceful 4-coloring of $G$ by coloring each clause gadget by one of the colorings in Figure 5 or a suitable angular rotation of them. ∎

Figure 4: A graceful 4-coloring $h$ of $G^{X}$.

Figure 5: Two graceful 4-colorings of $G^{C}$