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

Li Zhang, You Lu, Shenggui Zhang

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Article number113409
JournalDiscrete Mathematics
Volume346
Issue number8
DOIs
StatePublished - Aug 2023

Keywords

  • Critical signed graph
  • Edge coloring
  • Signed graph
  • Signed planar graph

Fingerprint

Dive into the research topics of 'Signed planar graphs with Δ ≥ 8 are Δ-edge-colorable'. Together they form a unique fingerprint.

Cite this