Yunfang Tang

The strong edge coloring of a graph G is an assignment of colors to the edges of G such that two distinct edges are colored differently if they are incident to a common edge or share an endpoint. The strong chromatic index of a graph G, denoted by ${\chi }_s^{\prime }(G)$, is the minimum number of colors needed for a strong edge coloring of G. In this paper, we prove the following two theorems: (1) If $G=T\cup C$ is a complete Halin graph with $\Delta =4$ that contains adjacent vertices of maximum degree, then ${\chi }_s^{\prime }(G)\le {\chi }_s^{\prime }(T)+1=2\Delta$. In particular, when T is a regular tree, ${\chi }_s^{\prime }(G)={\chi }_s^{\prime }(T)+1=2\Delta$. (2) If $G=T\cup C$ is a complete Halin graph with $\Delta \ge 5$ and $G\ne W_n$, then ${\chi }_s^{\prime }(G)={\chi }_s^{\prime }(T)=2\Delta -1$ when T is a regular tree. We extend the strong edge coloring results for complete cubic regular Halin graphs studied by W.C. Shiu and W.K. Tam, and improve the upper bound on the strong chromatic index of general Halin graphs established by Wei Yang and Baoyindureng Wu.

A strong edge coloring of a graph $G$ is an assignment of colors to the edges of $G$ such that two distinct edges are colored differently if they are incident to a common edge or share an endpoint. The strong chromatic index of a graph $G$, denoted by $χ_{s}'(G)$, is the minimum number of colors needed for a strong edge coloring of $G$. The edge weight of a graph $G$ is defined to be $\max\limits_{uv\in E(G)}\{(d_G(u)+d_G(v))\}$. It was proved in Chen et al in 2020 that every graph with edge weight at most 6 has a strong edge-coloring using at most 10 colors. In this paper, we consider the list version of strong edge-coloring. We strengthen this result by showing that every graph with edge weight at most 6 has a strong list-chromatic index at most 10. Specially, every subcubic graph has a strong list-chromatic index at most 10, which improves a result of Dai et al. in 2018.

A total weighting of a graph $G$ is a mapping $φ$ that assigns a weight to each vertex and each edge of $G$. The vertex-sum of $v \in V(G)$ with respect to $φ$ is $S_φ(v)=\sum_{e\in E(v)}φ(e)+φ(v)$. A total weighting is proper if adjacent vertices have distinct vertex-sums. A graph $G=(V,E)$ is called $(k,k')$-choosable if the following is true: If each vertex $x$ is assigned a set $L(x)$ of $k$ real numbers, and each edge $e$ is assigned a set $L(e)$ of $k'$ real numbers, then there is a proper total weighting $φ$ with $φ(y)\in L(y)$ for any $y \in V \cup E$. In this paper, we prove that the generalized Petersen graphs are $(1,3)$-choosable.