Back to Search
Start Over
List strong edge-coloring of graphs with maximum degree 4
- Publication Year :
- 2018
- Publisher :
- arXiv, 2018.
-
Abstract
- A strong edge-coloring of a graph $G$ is an edge-coloring such that any two edges on a path of length three receive distinct colors. We denote the strong chromatic index by $\chi_{s}'(G)$ which is the minimum number of colors that allow a strong edge-coloring of $G$. Erd\H{o}s and Ne\v{s}et\v{r}il conjectured in 1985 that the upper bound of $\chi_{s}'(G)$ is $\frac{5}{4}\Delta^{2}$ when $\Delta$ is even and $\frac{1}{4}(5\Delta^{2}-2\Delta +1)$ when $\Delta$ is odd, where $\Delta$ is the maximum degree of $G$. The conjecture is proved right when $\Delta\leq3$. The best known upper bound for $\Delta=4$ is 22 due to Cranston previously. In this paper we extend the result of Cranston to list strong edge-coloring, that is to say, we prove that when $\Delta=4$ the upper bound of list strong chromatic index is 22.<br />Comment: 10 pages, 5 figures
- Subjects :
- Discrete mathematics
Conjecture
020206 networking & telecommunications
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Upper and lower bounds
Graph
Theoretical Computer Science
Combinatorics
Edge coloring
010201 computation theory & mathematics
0202 electrical engineering, electronic engineering, information engineering
FOS: Mathematics
Mathematics - Combinatorics
Discrete Mathematics and Combinatorics
Combinatorics (math.CO)
Mathematics
Subjects
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....f973296f2d0275660e2b01367e83e234
- Full Text :
- https://doi.org/10.48550/arxiv.1801.06758