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$.

Back to all abstracts