Claw-free Graph - Structure

Structure

Chudnovsky & Seymour (2005) overview a series of papers in which they prove a structure theory for claw-free graphs, analogous to the graph structure theorem for minor-closed graph families proven by Robertson and Seymour, and to the structure theory for perfect graphs that Chudnovsky, Seymour and their co-authors used to prove the strong perfect graph theorem. The theory is too complex to describe in detail here, but to give a flavor of it, it suffices to outline two of their results. First, for a special subclass of claw-free graphs which they call quasi-line graphs (equivalently, locally co-bipartite graphs), they state that every such graph has one of two forms:

  1. A fuzzy circular interval graph, a class of graphs represented geometrically by points and arcs on a circle, generalizing proper circular arc graphs.
  2. A graph constructed from a multigraph by replacing each edge by a fuzzy linear interval graph. This generalizes the construction of a line graph, in which every edge of the multigraph is replaced by a vertex. Fuzzy linear interval graphs are constructed in the same way as fuzzy circular interval graphs, but on a line rather than on a circle.

Chudnovsky and Seymour classify arbitrary connected claw-free graphs into one of the following:

  1. Six specific subclasses of claw-free graphs. Three of these are line graphs, proper circular arc graphs, and the induced subgraphs of an icosahedron; the other three involve additional definitions.
  2. Graphs formed in four simple ways from smaller claw-free graphs.
  3. Antiprismatic graphs, a class of dense graphs defined as the claw-free graphs in which every four vertices induce a subgraph with at least two edges.

Much of the work in their structure theory involves a further analysis of antiprismatic graphs. The Schläfli graph, a claw-free strongly regular graph with parameters srg(27,16,10,8), plays an important role in this part of the analysis. This structure theory has led to new advances in polyhedral combinatorics and new bounds on the chromatic number of claw-free graphs, as well as to new fixed-parameter-tractable algorithms for dominating sets in claw-free graphs.

Read more about this topic:  Claw-free Graph

Famous quotes containing the word structure:

    “Women over fifty already form one of the largest groups in the population structure of the western world. As long as they like themselves, they will not be an oppressed minority. In order to like themselves they must reject trivialization by others of who and what they are. A grown woman should not have to masquerade as a girl in order to remain in the land of the living.”
    —Germaine Greer (b. 1939)

    “For the structure that we raise,
    Time is with materials filled;
    Our to-days and yesterdays
    Are the blocks with which we build.”
    —Henry Wadsworth Longfellow (1809–1882)

    “The verbal poetical texture of Shakespeare is the greatest the world has known, and is immensely superior to the structure of his plays as plays. With Shakespeare it is the metaphor that is the thing, not the play.”
    —Vladimir Nabokov (1899–1977)