✦ LIBER ✦

Kempe Equivalence of Edge-Colorings in Subcubic and Subquartic Graphs

✍ Scribed by Jessica McDonald; Bojan Mohar; Diego Scheide

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 190 KB
Volume: 70
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20613

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

It is proved that all 4‐edge‐colorings of a (sub)cubic graph are Kempe equivalent. This resolves a conjecture of the second author. In fact, it is found that the maximum degree Δ = 3 is a threshold for Kempe equivalence of (Δ+1)‐edge‐colorings, as such an equivalence does not hold in general when Δ = 4. One extra color allows a similar result in this latter case; however, namely, when Δ≤4 it is shown that all (Δ+2)‐edge‐colorings are Kempe equivalent. © 2011 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

Dependent edges in Mycielski graphs and

Dependent edges in Mycielski graphs and 4-colorings of 4-skeletons

✍ Karen L. Collins; Kimberly Tysdal 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB 👁 1 views

## Abstract A dependent edge in an acyclic orientation of a graph is one whose reversal creates a directed cycle. In answer to a question of Erdös, Fisher et al. [5] define __d__~min~(__G__) to be the minimum number of dependent edges of a graph __G__, where the minimum is taken over all acyclic or