Edited by R. A. Bailey
Publisher: Cambridge University Press
Print Publication Year: 1997
Online Publication Date:March 2010
Online ISBN:9780511662119
Paperback ISBN:9780521598408
Chapter DOI: http://dx.doi.org/10.1017/CBO9780511662119.006
Subjects: Discrete Mathematics Information Theory and Coding
Image View Extract Fullview: Text View | Enlarge Image ‹ Previous Chapter ›Next Chapter
Summary We discuss tree width, a new connectivity invariant of graphs defined by Robertson and Seymour. We present a duality result and a canonical decomposition theorem tied to this invariant. We also discuss a number of applications of these results, including Robertson and Seymour's Graph Minors Project.
Introduction
A taste of things to come
A graph is a set of vertices and an adjacency relation which indicates which pairs of vertices are joined by an edge. Thus, graph theory is essentially the study of connectivity. How then does one measure the connectivity of a graph?
Measuring the connectivity between two vertices is straightforward. Two vertices are said to be k-connected if there are k internally vertex disjoint paths between them. A classical theorem of Menger [30] states that vertices a and b are k-connected in a graph G precisely if there is no set X of fewer than k vertices such that a and b lie in different components of G – X. Standard alternating paths techniques, see e.g. [21], allow us to find either k internally vertex disjoint a-b paths or such a set X efficiently.
An appropriate definition of a highly connected graph, or of a highly connected piece of a graph is more difficult. The classical approach is to call a graph k-connected if every pair of its vertices is k-connected. This definition, although natural, does not capture the kind of connectivity that will concern us. It focuses on local properties rather than global ones.
pp. i-iv
pp. v-viii
pp. ix-xiv
pp. 1-12
The Harmonious Chromatic Number and the Achromatic Number : Read PDF
pp. 13-48
Computer Construction of Block Designs : Read PDF
pp. 49-64
Finite Quasiprimitive Graphs : Read PDF
pp. 65-86
Tree Width and Tangles: A New Connectivity Measure and Some Applications : Read PDF
pp. 87-162
Minor-monotone Graph Invariants : Read PDF
pp. 163-196
Some Applications of Algebraic Curves in Finite Geometry and Combinatorics : Read PDF
pp. 197-236
New Perspectives on Interval Orders and Interval Graphs : Read PDF
pp. 237-286
Approximate Counting : Read PDF
pp. 287-324
pp. 325-330
pp. 331-338