全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
Mathematics  2015 

On The Chromatic Number of Matching Graphs

Full-Text   Cite this paper   Add to My Lib

Abstract:

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.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133