Incidence Posets and Cover Graphs
classification
🧮 math.CO
keywords
graphsincidenceposetsansweringchromaticcoverdimensiongraph
read the original abstract
We prove two theorems concerning incidence posets of graphs, cover graphs of posets and a related graph parameter. First, answering a question of Haxell, we show that the chromatic number of a graph is not bounded in terms of the dimension of its incidence poset, provided the dimension is at least four. Second, answering a question of K\v{r}\'{i}\v{z} and Ne\v{s}et\v{r}il, we show that there are graphs with large girth and large chromatic number among the class of graphs having eye parameter at most two.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.