On the Chromatic Number of Matching Kneser Graphs

Meysam Alishahi, Hajiabolhassan Hossein*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

23 Downloads (Pure)

Abstract

In an earlier paper, the present authors (2015) introduced the altermatic number of graphs and used Tucker's lemma, an equivalent combinatorial version of the Borsuk-Ulam theorem, to prove that the altermatic number is a lower bound for chromatic number. A matching Kneser graph is a graph whose vertex set consists of all matchings of a specified size in a host graph and two vertices are adjacent if their corresponding matchings are edge-disjoint. Some well-known families of graphs such as Kneser graphs, Schrijver graphs and permutation graphs can be represented by matching Kneser graphs. In this paper, unifying and generalizing some earlier works by Lovász (1978) and Schrijver (1978), we determine the chromatic number of a large family of matching Kneser graphs by specifying their altermatic number. In particular, we determine the chromatic number of these matching Kneser graphs in terms of the generalized Turán number of matchings.

Original languageEnglish
JournalCombinatorics Probability and Computing
Volume29
Issue number1
Pages (from-to)1-21
ISSN0963-5483
DOIs
Publication statusPublished - 1 Jan 2019

Fingerprint Dive into the research topics of 'On the Chromatic Number of Matching Kneser Graphs'. Together they form a unique fingerprint.

Cite this