The strong chromatic index of 1-planar graphs
The chromatic index $\chi'(G)$ of a graph $G$ is the smallest $k$ for which $G$ admits an edge $k$-coloring such that any two adjacent edges have distinct colors. The strong chromatic index $\chi'_s(G)$ of $G$ is the smallest $k$ such that $G$ has an edge $k$-coloring with the condition that any two edges at distance at most 2 receive distinct colors. A graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. In this paper, we show that every graph $G$ with maximum average degree $\bar{d}(G)$ has $\chi'_{s}(G)\le (2\bar{d}(G)-1)\chi'(G)$. As a corollary, we prove that every 1-planar graph $G$ with maximum degree $\Delta$ has $\chi'_{\rm s}(G)\le 14\Delta$, which improves a result, due to Bensmail et al., which says that $\chi'_{\rm s}(G)\le 24\Delta$ if $\Delta\ge 56$.
Authors
- Ning Song (ORCID: https://orcid.org/0000-0003-1233-6890)
- Jianfeng Wang (ORCID: https://orcid.org/0000-0003-3080-6657)
- Weifan Wang (ORCID: https://orcid.org/0000-0001-8518-6630)
- Yiqiao Wang (ORCID: https://orcid.org/0000-0002-5322-1312)
Institutions
- Shandong University of Technology (CN)
- Beijing University of Technology (CN)
Publication Details
- Journal
- Discrete Mathematics & Theoretical Computer Science
- Published
- 2025-01-16
- DOI
- https://doi.org/10.46298/dmtcs.9631
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Natural Science Foundation of China