Signed planar graphs with Δ ≥ 8 are Δ-edge-colorable

Li Zhang, You Lu, Shenggui Zhang

科研成果: 期刊稿件文章同行评审

摘要

A well-known theorem due to Vizing states that every graph with maximum degree Δ is Δ- or (Δ+1)-edge-colorable. Recently, Behr extended the concept of edge coloring in a natural way to signed graphs. He also proved that an analogue of Vizing's Theorem holds for all signed graphs. Adopting Behr's definition, Zhang et al. proved that a signed planar graph G with maximum degree Δ is Δ-edge-colorable if either Δ≥10 or Δ∈{8,9} and G contains no adjacent triangles. They also proposed the conjecture that every signed planar graph with Δ≥6 is Δ-edge-colorable, as a generalization of Vizing's Planar Graph Conjecture. In this paper, we prove that every signed planar graph with Δ≥8 is Δ-edge-colorable.

源语言英语
文章编号113409
期刊Discrete Mathematics
346
8
DOI
出版状态已出版 - 8月 2023

指纹

探究 'Signed planar graphs with Δ ≥ 8 are Δ-edge-colorable' 的科研主题。它们共同构成独一无二的指纹。

引用此