-
Graceful coloring is computationally hard
Authors:
Cyriac Antony,
Laavanya D.,
Devi Yamini S
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 c…
▽ More
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 $χ_g(G)$.
We prove that $χ(G^2)\leq χ_g(G)\leq a(χ(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.
△ Less
Submitted 2 July, 2024;
originally announced July 2024.
-
An Analysis of Graceful Coloring in a Specific r-Regular Graphs
Authors:
Laavanya D.,
Devi Yamini S.
Abstract:
A graceful $l$-coloring of a graph $G$ is a proper vertex coloring with $l$ colors which induces a proper edge coloring with at most $l-1$ colors, where the color for an edge $ab$ is the absolute difference between the colors assigned to the vertices $a$ and $b$. The graceful chromatic number $χ_g(G)$ is the smallest $l$ for which $G$ permits graceful $l$-coloring. The problem of computing the gra…
▽ More
A graceful $l$-coloring of a graph $G$ is a proper vertex coloring with $l$ colors which induces a proper edge coloring with at most $l-1$ colors, where the color for an edge $ab$ is the absolute difference between the colors assigned to the vertices $a$ and $b$. The graceful chromatic number $χ_g(G)$ is the smallest $l$ for which $G$ permits graceful $l$-coloring. The problem of computing the graceful chromatic number of regular graphs is still open, though the existence of the lower bound was proved in \cite{3}. Hence, we pay attention to the computation of the graceful chromatic number of a special class of regular graphs namely complete graphs using set theoretic approach. Also, a few characterization of graphs based on their graceful chromatic number were examined.
△ Less
Submitted 28 June, 2024;
originally announced June 2024.
-
Antimagic Labeling of Generalized Edge Corona Graphs
Authors:
Nivedha D,
Devi Yamini S
Abstract:
An antimagic labeling of a graph $G$ is a one-to-one correspondence between the edge set $E(G)$ and $\lbrace 1,2,...,|E(G)|\rbrace$ in which the sum of the edge labels incident on the distinct vertices are distinct. Let $G$,$H_1$,$H_2$,...,$H_{m-1}$, and $H_m$ be simple graphs where $|E(G)|=m$. A generalized edge corona of the graph $G$ and $(H_1,H_2,...,H_m)$ (denoted by…
▽ More
An antimagic labeling of a graph $G$ is a one-to-one correspondence between the edge set $E(G)$ and $\lbrace 1,2,...,|E(G)|\rbrace$ in which the sum of the edge labels incident on the distinct vertices are distinct. Let $G$,$H_1$,$H_2$,...,$H_{m-1}$, and $H_m$ be simple graphs where $|E(G)|=m$. A generalized edge corona of the graph $G$ and $(H_1,H_2,...,H_m)$ (denoted by $G\diamond (H_1,H_2,...H_m)$) is a graph obtained by taking a copy of $G,H_1,H_2,...,H_m$ and joining the end vertices of $i^{th}$ edge of $G$ to every vertex of $H_i$, $i\in\lbrace 1,2,...,m\rbrace$. In this paper, we consider $G$ as a connected graph with exactly one vertex of maximum degree 3 (excluding the spider graph with exactly one vertex of maximum degree 3 containing uneven legs) and each $H_i$, $1\leq i \leq m$ as a connected graph on at least two vertices. We provide an algorithmic approach to prove that $G$ $\diamond$ $(H_1,H_2,...H_m)$ is antimagic under certain conditions.
△ Less
Submitted 17 November, 2023;
originally announced November 2023.
-
Local Distance Antimagic Vertex Coloring of Graphs
Authors:
Divya T,
Devi Yamini S
Abstract:
A bijective function $f:V\rightarrow\left\{1,2,3,...,|V| \right\}$ is said to be a local distance antimagic labeling of a graph $G=(V,E)$, if $w(u)\neq w(v)$ for any two adjacent vertices $u, v$ where the weight $w(v)=\sum_{z\in N(v)}f(z)$. The local distance antimagic labeling of $G$ induces a proper coloring in $G$, called local distance antimagic chromatic number denoted by $χ_{ld}(G)$. In this…
▽ More
A bijective function $f:V\rightarrow\left\{1,2,3,...,|V| \right\}$ is said to be a local distance antimagic labeling of a graph $G=(V,E)$, if $w(u)\neq w(v)$ for any two adjacent vertices $u, v$ where the weight $w(v)=\sum_{z\in N(v)}f(z)$. The local distance antimagic labeling of $G$ induces a proper coloring in $G$, called local distance antimagic chromatic number denoted by $χ_{ld}(G)$. In this article, we introduce the parameter $χ_{ld}(G)$ and compute the local distance antimagic chromatic number of graphs.
Keywords: Distance antimagic labeling, Local distance antimagic labeling, Local distance antimagic chromatic number.
△ Less
Submitted 3 June, 2021;
originally announced June 2021.
