𝔖 Bobbio Scriptorium
✦   LIBER   ✦

General results on tolerance intersection graphs

✍ Scribed by M. S. Jacobson; F. R. McMorris; E. R. Scheinerman

Publisher
John Wiley and Sons
Year
1991
Tongue
English
Weight
255 KB
Volume
15
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this paper, general results are presented that are related to ϕ‐tolerance intersection graphs previously defined by Jacobson, McMorris, and Mulder. For example, it is shown that all graphs are ϕ‐tolerance intersection graphs for all Ο•, yet for β€œnice” Ο•, almost no graphs are ϕ‐tolerance interval graphs. Additional results about representation of trees are given.

πŸ“œ SIMILAR VOLUMES

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

On planar intersection graphs with forbi
On planar intersection graphs with forbidden subgraphs
✍ JΓ‘nos Pach; Micha Sharir πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 154 KB

## Abstract Let ${\cal C}$ be a family of __n__ compact connected sets in the plane, whose intersection graph $G({\cal C})$ has no complete bipartite subgraph with __k__ vertices in each of its classes. Then $G({\cal C})$ has at most __n__ times a polylogarithmic number of edges, where the exponent

General Partitioning on Random Graphs
General Partitioning on Random Graphs
✍ C.R. Subramanian; C.E. Veni Madhavan πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 158 KB

Consider the general partitioning (GP) problem defined as follows: Partition the vertices of a graph into k parts W 1 W k satisfying a polynomial time verifiable property. In particular, consider properties (introduced by T. Feder, P. Hell, S. Klein, and R. Motwani, in "Proceedings of the Annual ACM

Various results on the toughness of grap
Various results on the toughness of graphs
✍ Broersma, Hajo; Engbers, Erik; Trommel, Huib πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 90 KB πŸ‘ 2 views

Let G be a graph and let t Υ† 0 be a real number. Then, We discuss how the toughness of (spanning) subgraphs of G and related graphs depends on (G), we give some sufficient degree conditions implying that (G) Υ† t, and we study which subdivisions of 2-connected graphs have minimally 2-tough squares.

Some results on odd factors of graphs
Some results on odd factors of graphs
✍ Cui Yuting; Mikio Kano πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 245 KB πŸ‘ 1 views