On the chromatic number of matching Kneser graphs

DOI10.1017/S0963548319000178zbMATH Open1439.05076arXiv1507.08456OpenAlexW2972707657WikidataQ127243333 ScholiaQ127243333MaRDI QIDQ5222567FDOQ5222567

Authors: Meysam Alishahi, Hajiabolhassan Hossein 

Publication date: 6 April 2020

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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 work available at URL: https://arxiv.org/abs/1507.08456

Recommendations

• A generalization of Kneser's conjecture
• Chromatic number of random Kneser hypergraphs
• Topological lower bounds for the chromatic number: a hierarchy
• On the chromatic number of general Kneser hypergraphs
• Chromatic number via Turán number

zbMATH Keywords

chromatic numberaltermatic numbermatching Kneser graphgeneralized Turán number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Cites Work

• Tiling Turán theorems
• The minimum degree threshold for perfect graph packings
• Embedding spanning bipartite graphs of small bandwidth
• The Factorization of Linear Graphs
• Proof of the Alon-Yuster conjecture
• Title not available (Why is that?)
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
• Kneser's conjecture, chromatic number, and homotopy
• A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
• Structure of independent sets in direct products of some vertex-transitive graphs
• The Chromatic Number of Kneser Hypergraphs
• Title not available (Why is that?)
• Intersecting families of permutations
• An Erdős--Ko--Rado theorem for partial permutations
• Local chromatic number, Ky Fan's theorem, and circular colorings
• Generalized Kneser coloring theorems with combinatorial proofs
• A short proof for Chen's alternative Kneser coloring lemma
• A new coloring theorem of Kneser graphs
• Hamiltonian degree sequences in digraphs
• Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen
• Title not available (Why is that?)
• On the chromatic number of general Kneser hypergraphs
• Box complexes, neighborhood complexes, and the chromatic number
• Colourful theorems and indices of homomorphism complexes
• Chromatic number via Turán number
• Bipartite graph tiling
• On chromatic number and minimum cut

Cited In (4)

• Chromatic number via Turán number
• On the chromatic number of a subgraph of the Kneser graph
• Counterexamples to a conjecture on matching Kneser graphs
• Concerning a conjecture on matching Kneser graphs

This page was built for publication: On the chromatic number of matching Kneser graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5222567)