2015/07/30 by Meysam Alishahi, Alishahi, Meysam, Hossein Hajiabolhassan +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis #math.CO #msc:05C15
paper · pdf · doi:10.48550/arxiv.1507.08456
arXiv admin note: substantial text overlap with arXiv:1403.4404
arxiv created 2015/07/30 · arxiv updated 2015/07/31
In an earlier paper, the present authors (2013) introduced the altermatic number of graphs and used Tucker's Lemma, an equivalent combinatorial version of the Borsuk-Ulam Theorem, to show that the altermatic number is a lower bound for the chromatic number. A matching graph has the set of all matchings of a specified size of a graph as vertex set and two vertices are adjacent if the corresponding matchings are edge-disjoint. It is known that the Kneser graphs, the Schrijver graphs, and the permutation graphs can be represented by matching graphs. In this paper, as a generalization of the well-known result of Schrijver about the chromatic number of Schrijver graphs, we determine the chromatic number of a large family of matching graphs by specifying their altermatic number. In particular, we determine the chromatic number of these matching graphs in terms of the generalized Turan number of matchings.