Covering and coloring polygon-circle graphs. (English) Zbl 0871.05025
Summary: 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 \(\alpha\log\alpha\) for the clique covering number is asymptotically best possible. For chromatic number, the upper bound we prove is of order \(2^\omega\), which is better than previously known upper bounds for circle graphs.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C35 | Extremal problems in graph theory |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
Keywords:
overlap graphs; intersection graphs; polygons; binding functions; chromatic number; clique covering number; polygon-circle graphs; independence numbers; circle graphsReferences:
| [1] | Bouchet, A., Reducing prime graphs and recognizing circle graphs, Combinatorica, 7, 243-254 (1987) · Zbl 0666.05037 |
| [2] | Bouchet, A., Circle graph obstructions, J. Combin. Theory Ser. B, 60, 107-144 (1994) · Zbl 0793.05116 |
| [3] | Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054 |
| [4] | Gyarfäs, A., On the chromatic number of multiple interval graphs and overlap graphs, Discrete Math., 55, 161-166 (1985) · Zbl 0569.05019 |
| [5] | Gyarfäs, A., Corrigendum, Discrete Math., 62, 333 (1986) · Zbl 0598.05034 |
| [6] | Gyarfäs, A., Problems from the world surrounding perfect graphs, Zastos. Mat., 19, 413-441 (1987) · Zbl 0718.05041 |
| [7] | Janson, S.; Kratochvil, J., Threshold functions for classes of intersection graphs, Discrete Math., 108, 307-326 (1992) · Zbl 0769.05084 |
| [8] | Koebe, M., On a new class of intersection graphs, (Fiedler, M.; Nešetřil, J., Graphs and Complexity, Proc. 4th Czechoslovak Symp. on Combinatorics. Graphs and Complexity, Proc. 4th Czechoslovak Symp. on Combinatorics, Prachatice, 1992. Graphs and Complexity, Proc. 4th Czechoslovak Symp. on Combinatorics. Graphs and Complexity, Proc. 4th Czechoslovak Symp. on Combinatorics, Prachatice, 1992, Annals of Discrete Math., Vol. 51 (1992), North-Holland: North-Holland Amsterdam), 141-143 · Zbl 0767.05079 |
| [9] | Kostochka, A., On upper bounds on the chromatic numbers of graphs, (Transactions of the Institute of Mathematics, Vol. 10 (1988), Siberian Branch of the Academy of Sciences of USSR), 204-226, (in Russian) · Zbl 0677.05027 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
