Counterexamples to a conjecture on matching Kneser graphs

Let G be a graph and r\in\mathbb{N}. The matching Kneser graph \textsf{KG}(G, rK_۲) 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., ۲۹, No. ۱ (۲۰۲۰), ۱--۲۱] it was conjectured that for any connected graph G and positive integer r\geq ۲, the chromatic number of \textsf{KG}(G, rK_۲) is equal to |E(G)|-\textsf{ex}(G,rK_۲), where \textsf{ex}(G,rK_۲) 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.

Keywords:

matching Kneser graph , snarks , chromatic number