✦ LIBER ✦

Separation index of a graph

✍ Scribed by Andrew Vince

Publisher: John Wiley and Sons
Year: 2002
Tongue: English
Weight: 89 KB
Volume: 41
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10053

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The concepts of separation index of a graph and of a surface are introduced. We prove that the separation index of the sphere is 3. Also the separation index of any graph faithfully embedded in a surface of genus g is bounded by a funtion of g. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 53–61, 2002

📜 SIMILAR VOLUMES

A construction of chromatic index critic

A construction of chromatic index critical graphs

✍ Hian Poh Yap 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

## Abstract We prove that if __K__ is an undirected, simple, connected graph of even order which is of class one, regular of degree __p__ ≥ 2 and such that the subgraph induced by any three vertices is either connected or null, then any graph __G__ obtained from __K__ by splitting any vertex is __p

A generalized construction of chromatic

A generalized construction of chromatic index critical graphs from bipartite graphs

✍ Michael Plantholt 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 378 KB

W e prove that any graph with maximum degree n which can be obtained by removing exactly 2n -1 edges from the join K? -K, ,, is n-critical This generalizes special constructions of critical graphs by S Fiorini and H P Yap, and suggests a possible extension of another general construction due to Yap

On matroid separations of graphs

✍ Klaus Truemper 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 308 KB

Let K be a connected and undirected graph, and M be the polygon matroid of K . Assume that, for some k 2 1, the matroid M is kseparable and k-connected according to the matroid separability and connectivity definitions of W. T. Tutte. In this paper we classify the matroid kseparations of M in terms

Graphs and Separability Properties of Gr

Graphs and Separability Properties of Groups

✍ Rita Gitik 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 207 KB

A group G is LERF locally extended residually finite if for any finitely generated subgroup S of G and for any g f S there exists a finite index subgroup S of G which contains S but not g. Using graph-theoretical methods we give 0 algorithms for constructing finite index subgroups in amalgamated fre

Strong chromatic index of subset graphs

✍ Quinn, Jennifer J.; Benjamin, Arthur T. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 2 views

The strong chromatic index of a graph G, denoted sq(G), is the minimum number of parts needed to partition the edges of G into induced matchings. For 0 ≤ k ≤ l ≤ m, the subset graph S m (k, l) is a bipartite graph whose vertices are the kand l-subsets of an m element ground set where two vertices ar

The chromatic index of graphs with a spa

The chromatic index of graphs with a spanning star

✍ Mike Plantholt 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 468 KB 👁 1 views

## Abstract Vizing's Theorem states that any graph __G__ has chromatic index either the maximum degree Δ(__G__) or Δ(__G__) + 1. If __G__ has 2~s~ + 1 points and Δ(__G__) = 2s, a well‐known necessary condition for the chromatic index to equal 2~s~ is that __G__ have at most 2s^2^ lines. Hilton conj