On the chromatic number of matching Kneser graphs

DOI10.1017/S0963548319000178MaRDI QIDQ5222567zbMATH OpenOpenAlexWikidataFDO

Authors Meysam Alishahi, Hajiabolhassan Hossein

Publication date 6 April 2020

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

Full work available at URL https://arxiv.org/abs/1507.08456

zbMATH Keywords

chromatic numberaltermatic numbermatching Kneser graphgeneralized Turán number

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 3141016 (Why is no real title available?)
• scientific article; zbMATH DE number 3672329 (Why is no real title available?)
• scientific article; zbMATH DE number 1355293 (Why is no real title available?)
• A new coloring theorem of Kneser graphs
• A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
• A short proof for Chen's alternative Kneser coloring lemma
• An Erdős--Ko--Rado theorem for partial permutations
• Bipartite graph tiling
• Box complexes, neighborhood complexes, and the chromatic number
• Chromatic number via Turán number
• Colourful theorems and indices of homomorphism complexes
• Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen
• Embedding spanning bipartite graphs of small bandwidth
• Generalized Kneser coloring theorems with combinatorial proofs
• Hamiltonian degree sequences in digraphs
• Intersecting families of permutations
• Kneser's conjecture, chromatic number, and homotopy
• Local chromatic number, Ky Fan's theorem, and circular colorings
• On chromatic number and minimum cut
• On the chromatic number of general Kneser hypergraphs
• Proof of the Alon-Yuster conjecture
• Structure of independent sets in direct products of some vertex-transitive graphs
• The Chromatic Number of Kneser Hypergraphs
• The Factorization of Linear Graphs
• The minimum degree threshold for perfect graph packings
• Tiling Turán theorems
• 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

Cited in

(4)

• Chromatic number via Turán number
• Counterexamples to a conjecture on matching Kneser graphs
• On the chromatic number of a subgraph of the Kneser graph
• 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)