%0 Journal Article
%T Counterexamples to a conjecture on matching Kneser graphs
%J Transactions on Combinatorics
%I University of Isfahan
%Z 2251-8657
%A N. Iradmusa, Moharram
%D 2023
%\ 09/01/2023
%V 12
%N 3
%P 172-173
%! Counterexamples to a conjecture on matching Kneser graphs
%K matching Kneser graph
%K snarks
%K chromatic number
%R 10.22108/toc.2022.132638.1961
%X 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.
%U https://toc.ui.ac.ir/article_26847_9307b1b5b45d7de0418b8b8b2bb530fc.pdf