Incidence Posets and Cover Graphs |
| |
Authors: | William T. Trotter Ruidong Wang |
| |
Affiliation: | 1. School of Mathematics, Georgia Institute of Technology, Atlanta, GA, 30332, USA
|
| |
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?í? 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|