Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-22T19:08:17.507Z Has data issue: false hasContentIssue false

On the Chromatic Number of Matching Kneser Graphs

Published online by Cambridge University Press:  12 September 2019

Meysam Alishahi
Affiliation:
Faculty of Mathematical Sciences, Shahrood University of Technology, Iran
Hajiabolhassan Hossein*
Affiliation:
Department of Applied Mathematics and Computer Science, Technical University of Denmark, DK-2800 Lyngby, Denmark Department of Mathematical Sciences, Shahid Beheshti University, P.O. Box 19839-69411, Tehran, Iran
*
*Corresponding author. Email: [email protected]

Abstract

In an earlier paper, the present authors (2015) introduced the altermatic number of graphs and used Tucker’s lemma, an equivalent combinatorial version of the Borsuk–Ulam 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ász (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án number of matchings.

Type
Paper
Copyright
© Cambridge University Press 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Alishahi, M. and Hajiabolhassan, H. (2015) On the chromatic number of general Kneser hypergraphs. J. Combin. Theory Ser. B 115 186209.CrossRefGoogle Scholar
[2] Alishahi, M. and Hajiabolhassan, H. (2017) Chromatic number via Turán number. Discrete Math . 340 23662377.CrossRefGoogle Scholar
[3] Alishahi, M. and Hajiabolhassan, H. (2019) On chromatic number and minimum cut. J. Combin. Theory Ser. B. doi:10.1016/j.jctb.2019.02.007 CrossRefGoogle Scholar
[4] Alon, N., Frankl, P. and Lovász, L. (1986) The chromatic number of Kneser hypergraphs. Trans. Amer. Math. Soc. 298 359370.CrossRefGoogle Scholar
[5] Berge, C. (1958) Sur le couplage maximum d’un graphe. CR Acad. Sci. Paris 247 258259.Google Scholar
[6] Cameron, P. and Ku, C. (2003) Intersecting families of permutations. European J. Combin . 24 881890.CrossRefGoogle Scholar
[7] Chang, G., Liu, D. D.-F. and Zhu, X. (2013) A short proof for Chen’s Alternative Kneser Coloring Lemma. J. Combin. Theory Ser. A 120 159163.CrossRefGoogle Scholar
[8] Chen, P.-A. (2011) A new coloring theorem of Kneser graphs. J. Combin. Theory Ser. A 118 10621071.CrossRefGoogle Scholar
[9] Csorba, P., Lange, C., Schurr, I. and Wassmer, A. (2004) Box complexes, neighborhood complexes, and the chromatic number. J. Combin. Theory Ser. A 108 159168.CrossRefGoogle Scholar
[10] Dolnikov, V. (1988) A combinatorial inequality. Sibirsk. Mat. Zh. 29 5358, 219. Google Scholar
[11] Geng, X., Wang, J. and Zhang, H. (2012) Structure of independent sets in direct products of some vertex-transitive graphs. Acta Math. Sin. (Engl. Ser.) 28 697706.CrossRefGoogle Scholar
[12] Godsil, C. and Meagher, K. (2009), A new proof of the Erdös–Ko–Rado theorem for intersecting families of permutations. European J. Combin . 30 404414.CrossRefGoogle Scholar
[13] Huang, H., Lee, C. and Sudakov, B. (2012) Bandwidth theorem for random graphs. J. Combin. Theory Ser. B 102 1437.CrossRefGoogle Scholar
[14] Kneser, M. (1955) Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen. Math. Z. 61 429434.CrossRefGoogle Scholar
[15] Knox, F. and Treglown, A. (2013) Embedding spanning bipartite graphs of small bandwidth. Combin. Probab. Comput. 22 7196.CrossRefGoogle Scholar
[16] Komlós, J. (2000) Tiling Turán theorems. Combinatorica 20 203218.Google Scholar
[17] Komlós, J., Sárközy, G. and Szemerédi, E. (2001) Proof of the Alon–Yuster conjecture. Discrete Math . 235 255269.CrossRefGoogle Scholar
[18] , I. (1992) Equivariant cohomology and lower bounds for chromatic numbers. Trans. Amer. Math. Soc. 333 567577.Google Scholar
[19] Ku, C. and Leader, I. (2006) An Erdös–Ko–Rado theorem for partial permutations. Discrete Math . 306 7486.CrossRefGoogle Scholar
[20] Kühn, D. and Osthus, D. (2009) The minimum degree threshold for perfect graph packings. Combinatorica 29 65107.CrossRefGoogle Scholar
[21] Kühn, D., Osthus, D. and Treglown, A. (2010) Hamiltonian degree sequences in digraphs. J. Combin. Theory Ser. B 100 367380.CrossRefGoogle Scholar
[22] Lindner, C. and Rosa, A. (1999) Monogamous decompositions of complete bipartite graphs, symmetric -squares, and self-orthogonal -factorizations. Australas. J. Combin. 20 251256.Google Scholar
[23] Lovász, L. (1978) Kneser’s conjecture, chromatic number, and homotopy. J. Combin. Theory Ser. A 25 319324.CrossRefGoogle Scholar
[24] Matoušek, J. (2003) Using the Borsuk–Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry, Universitext, Springer.Google Scholar
[25] Schrijver, A. (1978) Vertex-critical subgraphs of Kneser graphs. Nieuw Arch. Wisk. (3) 26 454461.Google Scholar
[26] Simonyi, G., Tardif, C. and Zsbán, A. (2013) Colourful theorems and indices of homomorphism complexes. Electron. J. Combin 20 P10.Google Scholar
[27] Simonyi, G. and Tardos, G. (2006) Local chromatic number, Ky Fan’s theorem and circular colorings. Combinatorica 26 587626.CrossRefGoogle Scholar
[28] Tutte, W. (1947) The factorization of linear graphs. J. Lond. Math. Soc. s1-22 107–111. CrossRefGoogle Scholar
[29] Zhao, Y. (2009) Bipartite graph tiling. SIAM J. Discrete Math . 23 888900.CrossRefGoogle Scholar
[30] Ziegler, G. (2002) Generalized Kneser coloring theorems with combinatorial proofs. Invent. Math. 147 671691.CrossRefGoogle Scholar