2013/08/12 by William T. Trotter, Trotter, William T., Ruidong Wang +1
Computer Science · Mathematics · #05C35 #06A10 #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.1308.2471
openalex publication_date 2013/08/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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říž and Nešetř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.