TY - JOUR
ID - 26847
TI - Counterexamples to a conjecture on matching Kneser graphs
JO - Transactions on Combinatorics
JA - TOC
LA - en
SN - 2251-8657
AU - N. Iradmusa, Moharram
AD - Department of Mathematical Sciences, Shahid Beheshti University.
Y1 - 2023
PY - 2023
VL - 12
IS - 3
SP - 172
EP - 173
KW - matching Kneser graph
KW - snarks
KW - chromatic number
DO - 10.22108/toc.2022.132638.1961
N2 - Let $G$ be a graph and $r\in\mathbb{N}$. The matching Kneser graph $\textsf{KG}(G, rK_2)$ is a graph whose vertex set is the set of $r$-matchings in $G$ and two vertices are adjacent if their corresponding matchings are edge-disjoint. In [M. Alishahi and H. Hajiabolhassan, On the Chromatic Number of Matching Kneser Graphs, Combin. Probab. and Comput., 29, No. 1 (2020), 1--21] it was conjectured that for any connected graph $G$ and positive integer $r\geq 2$, the chromatic number of $\textsf{KG}(G, rK_2)$ is equal to $|E(G)|-\textsf{ex}(G,rK_2)$, where $\textsf{ex}(G,rK_2)$ denotes the largest number of edges in $G$ avoiding a matching of size $r$. In this note, we show that the conjecture is not true for snarks.
UR - https://toc.ui.ac.ir/article_26847.html
L1 - https://toc.ui.ac.ir/article_26847_9307b1b5b45d7de0418b8b8b2bb530fc.pdf
ER -