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_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.

Counterexamples to a conjecture on matching Kneser graphs Keywords:

matching Kneser graph , snarks , chromatic number