{
  "id": "2107.04998",
  "version": "v1",
  "published": "2021-07-11T09:00:01.000Z",
  "updated": "2021-07-11T09:00:01.000Z",
  "title": "Counterexamples to a conjecture on matching Kneser graphs",
  "authors": [
    "Moharram N. Iradmusa"
  ],
  "comment": "1 page",
  "categories": [
    "math.CO"
  ],
  "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 [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\\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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-07-11T09:00:01.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C65"
    ],
    "keywords": [
      "matching kneser graph",
      "conjecture",
      "counterexamples",
      "chromatic number",
      "largest number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 1,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}