Geodesic
The strong chromatic index of 1-planar graphs
Discrete mathematics & theoretical computer science, Tome 25 (2023-2024) no. 1 Cet article a éte moissonné depuis la source Episciences

Voir la notice de l'article

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$. 
@article{DMTCS_2023_25_1_a17,
     author = {Wang, Yiqiao and Song, Ning and Wang, Jianfeng and Wang, Weifan},
     title = {The strong chromatic index of 1-planar graphs},
     journal = {Discrete mathematics & theoretical computer science},
     year = {2023-2024},
     volume = {25},
     number = {1},
     doi = {10.46298/dmtcs.9631},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.9631/}
}
TY  - JOUR
AU  - Wang, Yiqiao
AU  - Song, Ning
AU  - Wang, Jianfeng
AU  - Wang, Weifan
TI  - The strong chromatic index of 1-planar graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2023-2024
VL  - 25
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.9631/
DO  - 10.46298/dmtcs.9631
LA  - en
ID  - DMTCS_2023_25_1_a17
ER  - 
%0 Journal Article
%A Wang, Yiqiao
%A Song, Ning
%A Wang, Jianfeng
%A Wang, Weifan
%T The strong chromatic index of 1-planar graphs
%J Discrete mathematics & theoretical computer science
%D 2023-2024
%V 25
%N 1
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.9631/
%R 10.46298/dmtcs.9631
%G en
%F DMTCS_2023_25_1_a17
Wang, Yiqiao; Song, Ning; Wang, Jianfeng; Wang, Weifan. The strong chromatic index of 1-planar graphs. Discrete mathematics & theoretical computer science, Tome 25 (2023-2024) no. 1. doi: 10.46298/dmtcs.9631

Cité par Sources :