Counterexamples to a conjecture on matching Kneser graphs

Document Type : Research Paper

Author

Department of Mathematical Sciences, Shahid Beheshti University.

Abstract

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.

Keywords

Main Subjects

References

[1] M. Alishahi and H. Hajiabolhassan, On the Chromatic Number of Matching Kneser Graphs, Combin. Probab. and
Comput., 29 (2020) 1–21.
[2] M. Gardner, Mathematical Games, Scientific American, 234 (1976) 126–130.
[3] L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A, 25 (1978) 319–324.
[4] J. Petersen, Die Theorie der regulären graphs, Acta Mathematica, 15 (1891) 193–220.
[5] T. Schönberger, Ein Beweis des Petersenschen Graphensatzes, Acta Sci. Math. (Szeged), 7 (1934-5) 51–57.
Transactions on Combinatorics
Volume 12, Issue 3 - Serial Number 3
September 2023
Pages 172-173

Files

Cited by

History

  • Receive Date: 07 February 2022
  • Revise Date: 18 August 2022
  • Accept Date: 21 August 2022
  • Published Online: 01 September 2023

Share

How to cite

Statistics