Edge colorings of planar graphs without 6-cycles with three chords (Q1746732)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Edge colorings of planar graphs without 6-cycles with three chords
scientific article

    Statements

    Edge colorings of planar graphs without 6-cycles with three chords (English)
    0 references
    0 references
    0 references
    25 April 2018
    0 references
    The edge-chromatic number $\chi\prime(G)$ of a graph $G$ is the minimum $k$ such that $G$ admits a proper $k$-edge-coloring. Vizing's theorem says that $\chi\prime(G)=\Delta(G)$ or $\Delta(G)+1$. If $\chi\prime(G) = \Delta(G)$, then $G$ is class 1, and it is class 2, otherwise. Vizing showed that for $k=2,3,4,5$ there is a planar graph with $\Delta=k$, which is class 2. He also proved that every planar graph with $\Delta\geq 8$ is class 1, and conjectured that every planar graph $G$ with $\Delta=6$ or 7 is class 1. \textit{V. G. Vizing}'s conjecture [Usp. Mat. Nauk 23, No. 6(144), 117--134 (1968; Zbl 0177.52301)] is proved for planar graphs with $\Delta=7$ and it is still open for the case $\Delta=6$, but some partial results are obtained. There is a series of papers, published in recent years, which prove that the conjecture is true for planar graphs with some additional restrictions. This paper is one of this type of papers. The authors prove that every planar graph is of class 1 if its maximum degree is at least 6 and any 6-cycle contains at most two chords. The authors prove this result using the discharging method.
    0 references
    0 references
    0 references
    0 references
    0 references
    edge coloring
    0 references
    planar graph
    0 references
    cycle
    0 references
    class 1
    0 references
    0 references