TY - JOUR
T1 - Covering and coloring polygon-circle graphs
AU - Kostochka, Alexandr
AU - Kratochvíl, Jan
N1 - Funding Information:
The first author (A.K.) was partially supported by the Russian Foundation for Fundamental Research, grant 93-01-01486, and by the Charles University Research Grant GAUK 351 and the second author (J.K.) by Research Grants GAUK 361 and GACR 2167. J.K. also acknowledges partial support from University of Newcastle, .Australia.
PY - 1997/1/15
Y1 - 1997/1/15
N2 - Polygon-circle graphs are intersection graphs of polygons inscribed in a circle. This class of graphs includes circle graphs (intersection graphs of chords of a circle), circular arc graphs (intersection graphs of arcs on a circle), chordal graphs and outerplanar graphs. We investigate binding functions for chromatic number and clique covering number of polygon-circle graphs in terms of their clique and independence numbers. The bound α log α for the clique covering number is asymptotically best possible. For chromatic number, the upper bound we prove is of order 2ω, which is better than previously known upper bounds for circle graphs.
AB - Polygon-circle graphs are intersection graphs of polygons inscribed in a circle. This class of graphs includes circle graphs (intersection graphs of chords of a circle), circular arc graphs (intersection graphs of arcs on a circle), chordal graphs and outerplanar graphs. We investigate binding functions for chromatic number and clique covering number of polygon-circle graphs in terms of their clique and independence numbers. The bound α log α for the clique covering number is asymptotically best possible. For chromatic number, the upper bound we prove is of order 2ω, which is better than previously known upper bounds for circle graphs.
UR - http://www.scopus.com/inward/record.url?scp=0012131407&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0012131407&partnerID=8YFLogxK
U2 - 10.1016/S0012-365X(96)00344-5
DO - 10.1016/S0012-365X(96)00344-5
M3 - Article
AN - SCOPUS:0012131407
SN - 0012-365X
VL - 163
SP - 299
EP - 305
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 1-3
ER -