This is a survey compiling results on strong edge-coloring and related coloring problems for squares of graphs in planar and sparse classes.
Strong edge-colouring of sparse planar graphs
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
A strong edge-colouring of a graph is a proper edge-colouring where each colour class induces a matching. It is known that every planar graph with maximum degree $\Delta$ has a strong edge-colouring with at most $4\Delta+4$ colours. We show that $3\Delta+1$ colours suffice if the graph has girth 6, and $4\Delta$ colours suffice if $\Delta\geq 7$ or the girth is at least 5. In the last part of the paper, we raise some questions related to a long-standing conjecture of Vizing on proper edge-colouring of planar graphs.
fields
math.CO 1years
2022 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Coloring, List Coloring, and Painting Squares of Graphs (and other related problems)
This is a survey compiling results on strong edge-coloring and related coloring problems for squares of graphs in planar and sparse classes.