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

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 6864669
Language Label Description Also known as
default for all languages
No label defined
    English
    Edge colorings of planar graphs without 6-cycles with three chords
    scientific article; zbMATH DE number 6864669

      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
      edge coloring
      0 references
      planar graph
      0 references
      cycle
      0 references
      class 1
      0 references

      Identifiers