Application in Graph Structure Theory
Clique-sums are important in graph structure theory, where they are used to characterize certain families of graphs as the graphs formed by clique-sums of simpler graphs. The first result of this type was a theorem of Wagner (1937), who proved that the graphs that do not have a five-vertex complete graph as a minor are the 3-clique-sums of planar graphs with the eight-vertex Wagner graph; this structure theorem can be used to show that the four color theorem is equivalent to the case k = 5 of the Hadwiger conjecture. The chordal graphs are exactly the graphs that can be formed by clique-sums of cliques without deleting any edges, and the strangulated graphs are the graphs that can be formed by clique-sums of cliques and maximal planar graphs without deleting edges. The graphs in which every induced cycle of length four or greater forms a minimal separator of the graph (its removal partitions the graph into two or more disconnected components, and no subset of the cycle has the same property) are exactly the clique-sums of cliques and maximal planar graphs, again without edge deletions. Johnson & McKee (1996) use the clique-sums of chordal graphs and series-parallel graphs to characterize the partial matrices having positive definite completions.
It is possible to derive a clique-sum decomposition for any graph family closed under graph minor operations: the graphs in every minor-closed family may be formed from clique-sums of graphs that are "nearly embedded" on surfaces of bounded genus, meaning that the embedding is allowed to omit a small number of apexes (vertices that may be connected to an arbitrary subset of the other vertices) and vortices (graphs with low pathwidth that replace faces of the surface embedding). These characterizations have been used as an important tool in the construction of approximation algorithms and subexponential-time exact algorithms for NP-complete optimization problems on minor-closed graph families.
Read more about this topic: Clique-sum
Famous quotes containing the words application, graph, structure and/or theory:
“It would be disingenuous, however, not to point out that some things are considered as morally certain, that is, as having sufficient certainty for application to ordinary life, even though they may be uncertain in relation to the absolute power of God.”
—René Descartes (1596–1650)
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)
“Science is intimately integrated with the whole social structure and cultural tradition. They mutually support one other—only in certain types of society can science flourish, and conversely without a continuous and healthy development and application of science such a society cannot function properly.”
—Talcott Parsons (1902–1979)
“Could Shakespeare give a theory of Shakespeare?”
—Ralph Waldo Emerson (1803–1882)