Back to Search
Start Over
Kempe Classes and Almost Bipartite Graphs
- Publication Year :
- 2023
-
Abstract
- Let $G$ be a graph and $k$ be a positive integer, and let $Kc(G, k)$ denote the number of Kempe equivalence classes for the $k$-colorings of $G$. In 2006, Mohar noted that $Kc(G, k) = 1$ if $G$ is bipartite. As a generalization, we show that $Kc(G, k) = 1$ if $G$ is formed from a bipartite graph by adding any number of edges less than $\binom{\lceil k/2\rceil}2+\binom{\lfloor k/2\rfloor}2$. We show that our result is tight (up to lower order terms) by constructing, for each $k \geq 8$, a graph $G$ formed from a bipartite graph by adding $(k^2+8k-45+1)/4$ edges such that $Kc(G, k) \geq 2$. This refutes a recent conjecture of Higashitani--Matsumoto.<br />Comment: 7 pages, 2 figures; 2nd version incorporates reviewer feedback
- Subjects :
- Mathematics - Combinatorics
05C15
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2303.09365
- Document Type :
- Working Paper