Chromatic number via Turán number

Publication: Research - peer-reviewJournal article – Annual report year: 2017

DOI

View graph of relations

For a graph G and a family of graphs F, the general Kneser graph KG(G, F) is a graph with the vertex set consisting of all subgraphs of G isomorphic to some member of F and two vertices are adjacent if their corresponding subgraphs are edge disjoint. In this paper, we introduce some generalizations of Turán number of graphs. In view of these generalizations, we give some lower and upper bounds for the chromatic number of general Kneser graphs KG(G, F). Using these bounds, we determine the chromatic number of some family of general Kneser graphs KG(G, F) in terms of generalized Turán number of graphs. In particular, we determine the chromatic number of every Kneser multigraph KG(G, F) where G is a multigraph each of whose edges has the multiplicity at least 2 and F is an arbitrary family of simple graphs. Moreover, the chromatic number of general Kneser graph KG(G, F) is exactly determined where G is a dense graph and F = {K1,2}
Original languageEnglish
JournalDiscrete Mathematics
Volume340
Issue number10
Pages (from-to)2366-2377
ISSN0012-365X
DOIs
StatePublished - 2017
CitationsWeb of Science® Times Cited: 0

    Keywords

  • Chromatic number, General Kneser graph, Generalized Turán number
Download as:
Download as PDF
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

ID: 134334031