2021/07/11 by Moharram N. Iradmusa, Iradmusa, Moharram N.
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO #msc:05C15 #msc:05C65
paper · pdf · doi:10.48550/arxiv.2107.04998
1 page
arxiv created 2021/07/11 · arxiv updated 2021/07/13
Let G be a graph and r∈ℕ. The matching Kneser graph \textsfKG(G, rK2) 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 [Alishahi, M. and Hajiabolhassan, H., On the Chromatic Number of Matching Kneser Graphs, Combin. Probab. and Comput. 29 (2020), no. 1, 1--21.] it was conjectured that for any connected graph G and positive integer r≥ 2, the chromatic number of \textsfKG(G, rK2) is equal to |E(G)|-\textsfex(G,rK2), where \textsfex(G,rK2) 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.