𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The maximal clique and colourability of curve contact graphs

✍ Scribed by Petr Hlineˇný

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
669 KB
Volume
81
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

Contact

graphs are a special kind of intersection graphs of geometrical objects in which the objects are not allowed to cross but only to touch each other. Contact graphs of simple curves, and line segments as a special case, in the plane are considered. The curve contact representations are studied with respect to the maximal clique and the chromatic number of the represented graphs. All possible curve contact representations of cliques are described, and a linear bound on chromatic number in the maximal clique size is proved for the curve contact graphs.

📜 SIMILAR VOLUMES

Maximal cliques in the Paley graph of sq
Maximal cliques in the Paley graph of square order
✍ R.D. Baker; G.L. Ebert; J. Hemmeter; A. Woldar 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 424 KB

Determining the clique number of the Paley graph of order q, 4 E I (mod 4) a prime power, is a difficult problem. However, the work of Blokhuis implies that in the Paley graph of order q2, where q is any odd prime power, the clique number is in fact q. In this paper we construct maximal cliques of s

Classes and Recognition of Curve Contact
Classes and Recognition of Curve Contact Graphs
✍ Petr Hliněný 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 737 KB

Contact graphs are a special kind of intersection graphs of geometrical objects in which the objects are not allowed to cross but only to touch each other. Contact graphs of simple curves, and line segments as a special case, in the plane are considered. Various classes of contact graphs are introdu