Kempe Classes and Almost Bipartite Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915048277934080 |
|---|---|
| author | Cranston, Daniel W. Feghali, Carl |
| author_facet | Cranston, Daniel W. Feghali, Carl |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_09365 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Kempe Classes and Almost Bipartite Graphs Cranston, Daniel W. Feghali, Carl Combinatorics 05C15 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. |
| title | Kempe Classes and Almost Bipartite Graphs |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2303.09365 |