Title of article :
Chromatic numbers of copoint graphs of convex geometries
Author/Authors :
Beagley، نويسنده , , Jonathan E. and Morris، نويسنده , , Walter، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2014
Pages :
7
From page :
151
To page :
157
Abstract :
We study the copoint graph of a convex geometry. We give a family of copoint graphs for which the ratio of the chromatic number to the clique number can be arbitrarily large. For any natural numbers 1 < d < k , we study the existence of a number K d ( k ) so that the chromatic number of the copoint graph of a convex geometry on a set of at least K d ( k ) elements, with every d -element subset closed, has chromatic number at least k . Our results are analogues of results of Erdős and Szekeres for convex geometries realizable by point sets in R d , where cliques in the copoint graph correspond to subsets of points in convex position.
Keywords :
chromatic number , Copoint graph , Convex geometry , Erd?s–Szekeres problem , Order dimension , clique number
Journal title :
Discrete Mathematics
Serial Year :
2014
Journal title :
Discrete Mathematics
Record number :
1600727
Link To Document :
بازگشت