zbMATH — the first resource for mathematics

On the chromatic number of some geometric type Kneser graphs. (English) Zbl 1067.05023
Summary: We estimate the chromatic number of graphs whose vertex set is the set of edges of a complete geometric graph on \(n\) points, and adjacency is defined in terms of geometric disjointness or geometric intersection.

05C15 Coloring of graphs and hypergraphs
PDF BibTeX Cite
Full Text: DOI
[1] Bárány, I., A short proof of Kneser’s conjecture, J. combin. theor. ser. A, 25, 325-326, (1978) · Zbl 0404.05028
[2] Hopf, H.; Pannwitz, E., Aufgabe no. 167, Jahresbericht der deutschen mathematiker-vereinigung, 43, 114, (1934) · JFM 61.0651.03
[3] Jensen, T.J.; Toft, B., Graph coloring problems, (1995), Wiley New York · Zbl 0855.05054
[4] Károlyi, G.; Pach, J.; Tóth, G., Ramsey-type results for geometric graphs. I, Discrete comput. geom., 18, 247-255, (1997) · Zbl 0940.05046
[5] Kneser, M., Aufgabe no. 360, Jahresbericht der deutschen mathematiker-vereinigung, 58, 2. Abteilung, 27, (1955)
[6] Kostochka, A.; Kratochvíl, J., Covering and coloring polygon-circle graphs, Discrete math., 163, 299-305, (1997) · Zbl 0871.05025
[7] Kupitz, Y., Extremal problems in combinatorial geometry, Aarhus university lecture notes series, vol. 53, (1979), Aarhus University Denmark · Zbl 0414.05029
[8] Lovász, L., Kneser’s conjecture, chromatic number, and homotopy, J. combin. theor. ser. A, 25, 319-324, (1978) · Zbl 0418.05028
[9] J. Matoušek, A combinatorial proof of Kneser’s conjecture, Combinatorica, submitted for publication
[10] Pach, J.; Agarwal, P.K., Combinatorial geometry, (1995), Wiley New York · Zbl 0881.52001
[11] Pach, J.; Törőcsik, J., Some geometric applications of Dilworth’s theorem, Discrete comput. geom., 12, 1-7, (1994) · Zbl 0799.05018
[12] Tóth, G., Note on geometric graphs, J. combin. theor. ser. A, 89, 126-132, (2000) · Zbl 0951.05028
[13] Tóth, G.; Valtr, P., Geometric graphs with few disjoint edges, Discrete comput. geom., 22, 633-642, (1999) · Zbl 0939.68097
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.