Choice number of Kneser graphs

DOI10.1016/J.DISC.2022.113097MaRDI QIDQ2166315zbMATH OpenOpenAlexFDO

Authors Vera Bulankina, Andrey B. Kupavskii

Publication date 24 August 2022

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

choice numberchromatic numberKneser graphsprobabilistic method

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: In this short note, we show that for any $epsilon>0$ and $k<n^{0.5-epsilon}$ the choice number of the Kneser graph $K{G}_{n,k}$ is $Theta(nlogn)$.

Recommendations

• Choice Numbers of Graphs: a Probabilistic Approach
• The Choice Number of Dense Random Graphs
• scientific article; zbMATH DE number 637317
• List coloring of complete multipartite graphs
• scientific article; zbMATH DE number 842014

Cites work

• A combinatorical proof of Kneser's conjecture
• A short proof of Kneser's conjecture
• Chromatic number of random Kneser hypergraphs
• Edge-critical subgraphs of Schrijver graphs. II: The general case
• scientific article; zbMATH DE number 3672329 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 3224335 (Why is no real title available?)
• Kneser's conjecture, chromatic number, and homotopy
• On random subgraphs of Kneser and Schrijver graphs
• Random Kneser graphs and hypergraphs
• The Chromatic Number of Kneser Hypergraphs

Cited in

(5)

• scientific article; zbMATH DE number 1241393 (Why is no real title available?)
• scientific article; zbMATH DE number 842014 (Why is no real title available?)
• Two questions on Kneser colorings
• Colouring complete multipartite and Kneser-type digraphs
• Colouring complete multipartite and Kneser-type digraphs (extended abstract)

This page was built for publication: Choice number of Kneser graphs

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