Publication

On random subgraphs of Kneser and Schrijver graphs

Andrei Kupavskii
2016
Article
Résumé

A Kneser graph KG(n,k) is a graph whose vertices are in oneto-one correspondence with k -element subsets of [n], with two vertices connected if and only if the corresponding sets do not intersect. A famous result due to Lowisz states that the chromatic number of a Kneser graph KG,k is equal to n 2k +2. In this paper we study the chromatic number of a random subgraph of a Kneser graph KG,,,k as n grows. A random sub graph KG, k(p) is obtained by including each edge of KO.,k with probability p. For a wide range of parameters k = k(n), p = p(n) we show that x(KG,,,,k (p)) is very close to x(KGn,k), w.h.p. differing by at most 4 in many cases. Moreover, we obtain the same bounds on the chromatic numbers for the so-called Schrijver graphs, which are known to be vertex -critical induced subgraphs of Kneser graphs. (C) 2016 Published by Elsevier Inc.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.