✦ LIBER ✦

Overlap number of graphs

✍ Scribed by Daniel W. Cranston; Nitish Korula; Timothy D. LeSaulnier; Kevin G. Milans; Christopher J. Stocker; Jennifer Vandenbussche; Douglas B. West

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 207 KB
Volume: 70
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20596

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

An overlap representation of a graph G assigns sets to vertices so that vertices are adjacent if and only if their assigned sets intersect with neither containing the other. The overlap number φ(G) (introduced by Rosgen) is the minimum size of the union of the sets in such a representation. We prove the following: (1) An optimal overlap representation of a tree can be produced in linear time, and its size is the number of vertices in the largest subtree in which the neighbor of any leaf has degree 2. (2) If δ(G)⩾2 and G≠K~3~, then φ(G)⩽|E(G)| − 1, with equality when G is connected and triangle‐free and has no star‐cutset. (3) If G is an n‐vertex plane graph with n⩾5, then φ(G)⩽2__n__ − 5, with equality when every face has length 4 and there is no star‐cutset. (4) If G is an n‐vertex graph with n⩾14, then φ(G)⩽n^2^/4 − n/2 − 1, with equality for even n when G arises from K~n/2, n/2~ by deleting a perfect matching. © 2011 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

On theP4-Structure of Perfect Graphs V.

On theP4-Structure of Perfect Graphs V. Overlap Graphs

✍ Chı&#x0301;nh T. Hoàng; Stefan Hougardy; Frédéric Maffray 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 480 KB

Given a graph G we define its k-overlap graph as the graph whose vertices are the induced P 4 's of G and two vertices in the overlap graph are adjacent if the corresponding P 4 's in G have exactly k vertices in common. For k=1, 2, 3 we prove that if the k-overlap graph of G is bipartite then G is

Numbers of cubic graphs

✍ R. W. Robinson; N. C. Wormald 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 223 KB

## Abstract The numbers of unlabeled cubic graphs on __p = 2n__ points have been found by two different counting methods, the best of which has given values for __p ≦__ 40.

Achromatic number of fragmentable graphs

✍ Keith Edwards 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB

## Abstract A __complete coloring__ of a simple graph __G__ is a proper vertex coloring such that each pair of colors appears together on at least one edge. The __achromatic number__ ψ(__G__) is the greatest number of colors in such a coloring. We say a class of graphs is fragmentable if for any po

Scattering number in graphs

✍ Shenggui Zhang; Ziguo Wang 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 75 KB 👁 1 views

Crossing numbers of imbalanced graphs

✍ János Pach; József Solymosi; Gábor Tardos 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 103 KB

## Abstract The __crossing number__, cr(__G__), of a graph __G__ is the least number of crossing points in any drawing of __G__ in the plane. According to the Crossing Lemma of M. Ajtai, V. Chvátal, M. Newborn, E. Szemerédi, Theory and Practice of Combinatorics, North‐Holland, Amsterdam, New York,

Path chromatic numbers of graphs

✍ Jin Akiyama; Hiroshi Era; Severino V. Gervacio; Mamoru Watanabe 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB