Chromatic number via Turán number

DOI10.1016/j.disc.2017.05.010zbMath1367.05062arXiv1401.0138OpenAlexW2963205604MaRDI QIDQ2012520

Meysam Alishahi, Hossein Hajiabolhassan

Publication date: 1 August 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numbergeneral Kneser graphgeneralized Turán number

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

Related Items

Chromatic number of random Kneser hypergraphs ⋮ Concerning a conjecture on matching Kneser graphs ⋮ Altermatic number of categorical product of graphs ⋮ Circular chromatic number of induced subgraphs of Kneser graphs ⋮ Biclique cover and local clique cover of graphs ⋮ Hedetniemi's conjecture for Kneser hypergraphs ⋮ On the Chromatic Number of Matching Kneser Graphs ⋮ On chromatic number and minimum cut

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Structure of independent sets in direct products of some vertex-transitive graphs
• Color the cycles
• Colorful subhypergraphs in Kneser hypergraphs
• On the chromatic number of general Kneser hypergraphs
• Kneser's conjecture, chromatic number, and homotopy
• An Erdős--Ko--Rado theorem for partial permutations
• Coloring the Cartesian sum of graphs
• A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
• Some simplified NP-complete graph problems
• On the maximum number of independent cycles in a graph
• Un problème de partition de l'ensemble des parties à trois éléments d'un ensemble fini
• On the chromatic number of the general Kneser-graph
• The Chromatic Number of Kneser Hypergraphs
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
• Chromatic Number of Cartesian Sum of Two Graphs
• On the maximal number of independent circuits in a graph
• Intersecting families of permutations
• Circular chromatic number: A survey