# On relaxed strong edge-coloring of graphs

###
Dan He

Department of mathematics, Southeast university

####
Wengsong Lin

Department of mathematics, Southeast university

PDF

**Minisymposium:**
VERTEX COLOURINGS AND FORBIDDEN SUBGRAPHS

**Content:**
Let $G$ be a graph. For two nonnegative integers $s$ and $t$, an
$(s,t)$-relaxed strong $k$-edge-coloring is an assignment of $k$
colors to the edges of $G$, such that for any edge $e$, there are at
most $s$ edges adjacent to $e$ and $t$ edges which are distance two
apart from $e$ assigned the same color as $e$. The $(s,t)$-relaxed
strong chromatic index, denoted by ${\chi'}_{(s,t)}(G)$, is the
minimum number $k$ of an $(s,t)$-relaxed strong $k$-edge-coloring
admitted by $G$. For a positive integer $\mu$, a
$\mu$-relaxed strong $k$-edge-coloring is an assignment of $k$
colors to the edges of $G$, such that for any edge $e$, there are at
most $\mu$ edges which are at most distance two
apart from $e$ assigned the same color as $e$. The
$\mu$-relaxed strong chromatic index, denoted by
${\chi'}_{(\mu)}(G)$, is the minimum number $k$ such that $G$ has a
$\mu$-relaxed strong $k$-edge-coloring.
This paper studies the $(s,t)$-relaxed strong edge-coloring of
graphs, especially trees. For a tree $T$, the tight upper bounds for
${\chi'}_{(s,0)}(T)$ and ${\chi'}_{(0,t)}(T)$ are given. And the
$(1,1)$-relaxed strong chromatic index of an infinite regular tree
is determined. Further results on ${\chi'}_{(1,0)}(T)$ are also
presented. Finally, the $\mu$-relaxed strong chromatic index is determined for almost $\mu$.