The chromatic number of finite type-graphs

DOI10.1016/J.JCTB.2016.10.004zbMATH Open1350.05028arXiv1603.05134OpenAlexW3099835900MaRDI QIDQ345136FDOQ345136

Vojtěch Rödl, Christian Avart, Bill Kay, Christian Reiher

Publication date: 25 November 2016

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: By a finite type-graph we mean a graph whose set of vertices is the set of all $k$-subsets of $[n]=1,2,ldots,n$ for some integers $ngekge1$, and in which two such sets are adjacent if and only if they realise a certain order type specified in advance. Examples of such graphs have been investigated in a great variety of contexts in the literature with particular attention being paid to their chromatic number. In recent joint work with Tomasz {L}uczak, two of the authors embarked on a systematic study of the chromatic numbers of such type-graphs, formulated a general conjecture determining this number up to a multiplicative factor, and proved various results of this kind. In this article we fully prove this conjecture.

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

zbMATH Keywords

chromatic numberorder types of pairsshift graphstype graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• The Ramsey property for graphs with forbidden complete subgraphs
• Note on decomposition of spheres in Hilbert spaces
• Shift graphs and lower bounds on Ramsey numbers \(r_ k(l;r)\)
• A Construction of Graphs without Triangles having Pre-Assigned Order and Chromatic Number
• Finite subgraphs of uncountably chromatic graphs
• On generalized shift graphs
• Teilmengen von Mengen mit Relationen
• Ordered Ramsey theory and track representations of graphs

Cited In (2)

• Hedetniemi's conjecture and adjoint functors in thin categories
• Independent sets in subgraphs of a shift graph

This page was built for publication: The chromatic number of finite type-graphs

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