✦ LIBER ✦

Characterizing intersection classes of graphs

✍ Scribed by Edward R. Scheinerman

Publisher: Elsevier Science
Year: 1985
Tongue: English
Weight: 571 KB
Volume: 55
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(85)90047-0

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is an intersection graph if it is possible to assign sets to its vertices so that adjacency corresponds exactly to nonempty intersection.

If the sets assigned to vertices must belong to a pre-specified family, the resulting class of all possible intersection graphs is called an intersection class. We characterize intersection classes. The main result is generalized for classes in which the assignment of sets to vertices must be one-to-one, as well as for classes of simplicial complexes arising as nerves of sets from a pre-specified family.

📜 SIMILAR VOLUMES

Intersection properties of graphs

✍ Terry A. McKee 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 550 KB

McKee, T.A., Intersection properties of graphs, Discrete Mathematics 89 (1991) 253-260. For each graph-theoretic property, we define a corresponding 'intersection property', motivated by the natural relationship of paths with interval graphs, and of trees with chordal graphs. We then develop a simp

Intersection Graphs of Segments

✍ J. Kratochvil; J. Matousek 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 998 KB

Intersection graphs of segments (the class SEG) and of other simple geometric objects in the plane are considered. The results fall into two main areas: how difficult is the membership problem for a given class and how large are the pictures needed to draw the representations. Among others, we prove

Intersections of graphs

✍ Béla Bollobás; Alex Scott 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 193 KB

Let G and H be two graphs of order n. If we place copies of G and H on a common vertex set, how much or little can they be made to overlap? The aim of this article is to provide some answers to this question, and to pose a number of related problems. Along the way, we solve a conjecture of Erd" os,

Forbidden configurations in intersection

Forbidden configurations in intersection graphs of r-graphs

✍ M.L. Gardner 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 335 KB

Characterizing subgraphs of Hamming grap

Characterizing subgraphs of Hamming graphs

✍ Sandi Klavžar; Iztok Peterin 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB

## Abstract Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph __G__ is an induced subgraph of a Hamming graph i

On set intersection representations of g

On set intersection representations of graphs

✍ Stasys Jukna 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 193 KB 👁 1 views

## Abstract The intersection dimension of a bipartite graph with respect to a type __L__ is the smallest number __t__ for which it is possible to assign sets __A__~__x__~⊆{1, …, __t__} of labels to vertices __x__ so that any two vertices __x__ and __y__ from different parts are adjacent if and only