On edge colorings of 1-planar graphs without 5-cycles with two chords (Q1717181)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On edge colorings of 1-planar graphs without 5-cycles with two chords |
scientific article |
Statements
On edge colorings of 1-planar graphs without 5-cycles with two chords (English)
0 references
7 February 2019
0 references
A graph is called 1-planar if it can be drawn in the plane so that each of its edges is crossed by at most one other edge. Let \(G\) be a 1-planar graph of maximum degree \(\Delta\). In this paper the following theorem is proved: If \(\Delta \geqslant 8\) and any 5-cycle of \(G\) has at most one chord, then \(G\) is edge-colorable with \(\Delta\) colors. This theorem weakens the hypotheses of a previous theorem of this type by \textit{X. Zhang} and \textit{G. Z. Liu} [Ars Comb. 104, 431--436 (2012; Zbl 1274.05186)]: If \(\Delta \geqslant 9\) and any 5-cycle of \(G\) has no chord at all, then \(G\) is edge-colorable with \(\Delta\) colors. \par The authors use their ``discharging method'' which requires a case-by-case analysis based on \textit{V. G. Vizing}'s adjacency lemma [Russ. Math. Surv. 23, No. 6, 125--141 (1968; Zbl 0192.60502); translation from Usp. Mat. Nauk 23, No. 6(144), 117--134 (1968)]. \par Notice that in the 1-planar case, the condition \(\Delta \geqslant 8\) is not a necessary one; for example, the complete four-partite graph \(K_{2,2,2,2}\) is 1-planar and is edge-colorable with \(\Delta = 6\) colors.
0 references
1-planar graph
0 references
edge-coloring
0 references
cycle
0 references
chord
0 references
Vizing's adjacency lemma
0 references
discharging method
0 references