The Edge-Distinguishing Chromatic Number of Petal Graphs, Chorded Cycles, and Spider Graphs

Abstract

The edge-distinguishing chromatic number (EDCN) of a graph $G$ is the minimum positive integer $k$ such that there exists a vertex coloring $c:V(G)\to \{1,2,\dots ,k\}$ whose induced edge labels $\{c(u),c(v)\}$ are distinct for all edges $uv$. Previous work has determined the EDCN of paths, cycles, and spider graphs with three legs. In this paper, we determine the EDCN of petal graphs with two petals and a loop, cycles with one chord, and spider graphs with four legs. These are achieved by graph embedding into looped complete graphs.

23 pages, 1 figure