{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,14]],"date-time":"2024-03-14T09:18:43Z","timestamp":1710407923062},"reference-count":30,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2019,9,12]],"date-time":"2019-09-12T00:00:00Z","timestamp":1568246400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In an earlier paper, the present authors (2015) introduced the<jats:italic>altermatic number<\/jats:italic>of graphs and used Tucker\u2019s lemma, an equivalent combinatorial version of the Borsuk\u2013Ulam 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\u00e1sz (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\u00e1n number of matchings.<\/jats:p>","DOI":"10.1017\/s0963548319000178","type":"journal-article","created":{"date-parts":[[2019,9,12]],"date-time":"2019-09-12T11:24:51Z","timestamp":1568287491000},"page":"1-21","source":"Crossref","is-referenced-by-count":1,"title":["On the Chromatic Number of Matching Kneser Graphs"],"prefix":"10.1017","volume":"29","author":[{"given":"Meysam","family":"Alishahi","sequence":"first","affiliation":[]},{"given":"Hajiabolhassan","family":"Hossein","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,9,12]]},"reference":[{"key":"S0963548319000178_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2019.02.007"},{"key":"S0963548319000178_ref25","unstructured":"Schrijver A. (1978) Vertex-critical subgraphs of Kneser graphs. Nieuw Arch. Wisk. (3) 26 454\u2013461."},{"key":"S0963548319000178_ref26","doi-asserted-by":"crossref","first-page":"P10","DOI":"10.37236\/2302","article-title":"Colourful theorems and indices of homomorphism complexes","volume":"20","author":"Simonyi","year":"2013","journal-title":"Electron. J. Combin"},{"key":"S0963548319000178_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.03.002"},{"key":"S0963548319000178_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.11.007"},{"key":"S0963548319000178_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(03)00078-7"},{"key":"S0963548319000178_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2010.08.008"},{"key":"S0963548319000178_ref4","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1986-0857448-8"},{"key":"S0963548319000178_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2015.05.010"},{"key":"S0963548319000178_ref16","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/s004930070020","article-title":"Tiling Tur\u00e1n theorems","volume":"20","author":"Koml\u00f3s","year":"2000","journal-title":"Combinatorica"},{"key":"S0963548319000178_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0034-x"},{"key":"S0963548319000178_ref18","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1090\/S0002-9947-1992-1081939-3","article-title":"Equivariant cohomology and lower bounds for chromatic numbers","volume":"333","author":"K\u017e","year":"1992","journal-title":"Trans. Amer. Math. Soc."},{"key":"S0963548319000178_ref28","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-22.2.107"},{"key":"S0963548319000178_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-009-2254-3"},{"key":"S0963548319000178_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90022-5"},{"key":"S0963548319000178_ref5","first-page":"258","article-title":"Sur le couplage maximum d\u2019un graphe","volume":"247","author":"Berge","year":"1958","journal-title":"CR Acad. Sci. Paris"},{"key":"S0963548319000178_ref30","doi-asserted-by":"publisher","DOI":"10.1007\/s002220100188"},{"key":"S0963548319000178_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2012.07.009"},{"key":"S0963548319000178_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2004.06.004"},{"key":"S0963548319000178_ref10","first-page":"53","article-title":"A combinatorial inequality","volume":"29","author":"Dolnikov","year":"1988","journal-title":"Sibirsk. Mat. Zh."},{"key":"S0963548319000178_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s10114-011-0311-5"},{"key":"S0963548319000178_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2008.05.006"},{"key":"S0963548319000178_ref29","doi-asserted-by":"publisher","DOI":"10.1137\/060665397"},{"key":"S0963548319000178_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2009.11.004"},{"key":"S0963548319000178_ref15","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000417"},{"key":"S0963548319000178_ref22","unstructured":"Lindner C. and Rosa A. (1999) Monogamous decompositions of complete bipartite graphs, symmetric -squares, and self-orthogonal -factorizations. Australas. J. Combin. 20 251\u2013256."},{"key":"S0963548319000178_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2017.05.010"},{"key":"S0963548319000178_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01181357"},{"key":"S0963548319000178_ref24","author":"Matou\u0161ek","year":"2003"},{"key":"S0963548319000178_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00279-X"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548319000178","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,20]],"date-time":"2021-01-20T06:19:15Z","timestamp":1611123555000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548319000178\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,12]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["S0963548319000178"],"URL":"https:\/\/doi.org\/10.1017\/s0963548319000178","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,12]]}}}