𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Intersections of graphs

✍ Scribed by Béla Bollobás; Alex Scott

Publisher
John Wiley and Sons
Year
2011
Tongue
English
Weight
193 KB
Volume
66
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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, Goldberg, Pach and Spencer.

📜 SIMILAR VOLUMES

Cross-intersecting couples of graphs
Cross-intersecting couples of graphs
✍ Emanuela Fachini; János Körner 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 134 KB

## Abstract Two graphs on the same vertex set form a cross‐intersecting couple if they have a pair of clique coverings with the property that every pair of cliques from the respective coverings intersect. In particular, a graph is called normal if it forms a cross‐intersecting couple with its compl

Intersections of longest cycles in grid
Intersections of longest cycles in grid graphs
✍ Menke, B.; Zamfirescu, T.; Zamfirescu, C. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 292 KB 👁 3 views

It is well-known that the largest cycles of a graph may have empty intersection. This is the case, for example, for any hypohamiltonian graph. In the literature, several important classes of graphs have been shown to contain examples with the above property. This paper investigates a (nontrivial) cl

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

Intersections of Longest Cycles in k-Con
Intersections of Longest Cycles in k-Connected Graphs
✍ Guantao Chen; Ralph J Faudree; Ronald J Gould 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 279 KB

Let G be a connected graph, where k 2. S. Smith conjectured that every two longest cycles of G have at least k vertices in common. In this note, we show that every two longest cycles meet in at least ck 3Â5 vertices, where cr0.2615. ## 1998 Academic Press In this note, we provide a lower bound on

Extremal Graphs for Intersecting Triangl
Extremal Graphs for Intersecting Triangles
✍ P. Erdos; Z. Furedi; R.J. Gould; D.S. Gunderson 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 400 KB

It is known that for a graph on \(n\) vertices \(\left\lfloor n^{2} / 4\right\rfloor+1\) edges is sufficient for the existence of many triangles. In this paper, we determine the minimum number of edges sufficient for the existence of \(k\) triangles intersecting in exactly one common vertex. C 1995

Simultaneous intersection representation
Simultaneous intersection representation of pairs of graphs
✍ Tanenbaum, Paul J. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 436 KB 👁 2 views

We characterize the pairs (G 1 , G 2 ) of graphs on a shared vertex set that are intersection polysemic: those for which the vertices may be assigned subsets of a universal set such that G 1 is the intersection graph of the subsets and G 2 is the intersection graph of their complements. We also cons