Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. The strong chromatic ...
Article

The strong chromatic index of 1-planar graphs

Yiqiao Wang, Ning Song, Jianfeng Wang, Weifan Wang
Download article
Open on arXiv
Submitted on
May 31, 2022
Accepted on
March 8, 2023
Published on
January 16, 2025
Last modified on
March 27, 2025
Volume 25
vol. 25:1
Graph Theory
DOI
10.46298/dmtcs.9631
License
Attribution 4.0 International (CC BY 4.0)
Indicators
1055
Views
768
Downloads

The strong chromatic index of 1-planar graphs

Yiqiao Wang, Ning Song, Jianfeng Wang, Weifan Wang
Abstract
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$.
Keywords
  • Mathematics - Combinatorics
Mathematics Subject Classification 2020
  • 05C10 - Planar graphs; geometric and topological aspects of graph theory
  • 05C15 - Coloring of graphs and hypergraphs
Preview
Loading PDF preview...