An adjacency lemma on signed edge colorings with an application to planar graphs
Li Zhang, Hajo J. Broersma, You Lu, Shenggui Zhang · Discrete Applied Mathematics · 2025
In the study of edge colorings of graphs, critical graphs are of particular importance. One classical result concerning the structure of critical graphs is known as Vizing’s Adjacency Lemma. This lemma provides useful structural information about the neighborhood of a vertex in a critical graph. Zhang introduced an adjacency lemma dealing with the second neighborhood of a vertex in a critical graph. Both of these adjacency lemmas are useful tools for proving classification results on edge colorings. In this paper, we present an adjacency lemma on critical signed graphs with even maximum degree. This new adjacency lemma can be interpreted as a local extension of Zhang’s Adjacency Lemma. As an application of the new lemma, we show that a signed planar graph with maximum degree Δ ≥ 6 in which every 6-cycle has at most one chord is Δ -edge-colorable.