Misplaced Pages

#66933

94-405: Chordal graphs are a subset of the perfect graphs . They may be recognized in linear time , and several problems that are hard on other classes of graphs such as graph coloring may be solved in polynomial time when the input is chordal. The treewidth of an arbitrary graph may be characterized by the size of the cliques in the chordal graphs that contain it. A perfect elimination ordering in

188-570: A and b of a given graph G , an ( a , b ) -separator S can be regarded as a predecessor of another ( a , b ) -separator T , if every path from a to b meets S before it meets T . More rigorously, the predecessor relation is defined as follows: Let S and T be two ( a , b ) -separators in G . Then S is a predecessor of T , in symbols S ⊑ a , b G T {\displaystyle S\sqsubseteq _{a,b}^{G}T} , if for each x ∈ S \ T , every path connecting x to b meets T . It follows from

282-404: A subtree graph , which is an intersection graph that has one vertex per subtree and an edge connecting any two subtrees that overlap in one or more nodes of the tree. Gavril showed that the subtree graphs are exactly the chordal graphs. A representation of a chordal graph as an intersection of subtrees forms a tree decomposition of the graph, with treewidth equal to one less than the size of

376-402: A vector x {\displaystyle x} that maximizes a linear objective function c ⋅ x {\displaystyle c\cdot x} , subject to the linear constraints x ≥ 0 {\displaystyle x\geq 0} and A x ≤ b {\displaystyle Ax\leq b} . Here, A {\displaystyle A}

470-427: A , b ) - separator if no proper subset of S separates a and b . More generally, S is called a minimal separator if it is a minimal separator for some pair ( a , b ) of nonadjacent vertices. Notice that this is different from minimal separating set which says that no proper subset of S is a minimal ( u , v ) -separator for any pair of vertices ( u , v ) . The following is a well-known result characterizing

564-1317: A 2-join, the complement of a 2-join, a homogeneous pair, or a skew partition . A partially ordered set is defined by its set of elements, and a comparison relation ≤ {\displaystyle \leq } that is reflexive (for all elements x {\displaystyle x} , x ≤ x {\displaystyle x\leq x} ), antisymmetric (if x ≤ y {\displaystyle x\leq y} and y ≤ x {\displaystyle y\leq x} , then x = y {\displaystyle x=y} , and transitive (if x ≤ y {\displaystyle x\leq y} and y ≤ z {\displaystyle y\leq z} , then x ≤ z {\displaystyle x\leq z} ). Elements x {\displaystyle x} and y {\displaystyle y} are comparable if x ≤ y {\displaystyle x\leq y} or y ≤ x {\displaystyle y\leq x} , and incomparable otherwise. For instance, set inclusion ( ⊆ {\displaystyle \subseteq } ) partially orders any family of sets . The comparability graph of

658-421: A chordal graph are colored in the order of an incremental construction sequence using a greedy coloring algorithm, the result will be an optimal coloring. The reverse of the vertex ordering used in this construction is called an elimination order . Similarly, if the vertices of a distance-hereditary graph are colored in the order of an incremental construction sequence, the resulting coloring will be optimal. If

752-399: A clique for each vertex v together with the neighbors of v that are later than v in the perfect elimination ordering, and test whether each of the resulting cliques is maximal. The clique graphs of chordal graphs are the dually chordal graphs . The largest maximal clique is a maximum clique, and, as chordal graphs are perfect, the size of this clique equals the chromatic number of

846-484: A common endpoint, and triangles in G {\displaystyle G} . In bipartite graphs, there are no triangles, so a clique cover in L ( G ) {\displaystyle L(G)} corresponds to a vertex cover in G {\displaystyle G} . Therefore, in line graphs of bipartite graphs, the independence number and clique cover number are equal. Induced subgraphs of line graphs of bipartite graphs are line graphs of subgraphs, so

940-451: A comparability graph, comes from a subset of elements that are all pairwise comparable; such a subset is called a chain , and it is linearly ordered by the given partial order. An independent set comes from a subset of elements no two of which are comparable; such a subset is called an antichain . For instance, in the illustrated partial order and comparability graph, { A , B , C } {\displaystyle \{A,B,C\}}

1034-493: A graph class is said to be χ-bounded if the chromatic number of the graphs in the class can be bounded by a function of their clique number. The perfect graphs are exactly the graphs for which this function is the identity , both for the graph itself and for all its induced subgraphs. The equality of the clique number and chromatic number in perfect graphs has motivated the definition of other graph classes, in which other graph invariants are set equal to each other. For instance,

SECTION 10

#1733086135067

1128-484: A graph is an ordering of the vertices of the graph such that, for each vertex v , v and the neighbors of v that occur after v in the order form a clique . A graph is chordal if and only if it has a perfect elimination ordering. Rose, Lueker & Tarjan (1976) (see also Habib et al. 2000 ) show that a perfect elimination ordering of a chordal graph may be found efficiently using an algorithm known as lexicographic breadth-first search . This algorithm maintains

1222-413: A graph is not perfect, it contains an odd cycle or its complement, and in these subgraphs the product of the clique number and independence number is one less than the number of vertices. The theory of perfect graphs developed from a 1958 result of Tibor Gallai that in modern language can be interpreted as stating that the complement of a bipartite graph is perfect; this result can also be viewed as

1316-504: A long odd cycle had only one chord, the two parts of the cycle between the endpoints of the chord would be induced paths of different parity. The prism over any parity graph (its Cartesian product with a single edge) is another parity graph, and the parity graphs are the only graphs whose prisms are perfect. Perfect graphs are closely connected to the theory of linear programming and integer programming . Both linear programs and integer programs are expressed in canonical form as seeking

1410-442: A matrix A {\displaystyle A} defined in this way from a perfect graph, the vectors x {\displaystyle x} satisfying the system of inequalities x ≥ 0 {\displaystyle x\geq 0} , A x ≤ 1 {\displaystyle Ax\leq 1} form an integral polytope . It is the convex hull of the indicator vectors of independent sets in

1504-404: A non-adjacent clique vertex. Therefore, these graphs have equal clique numbers and chromatic numbers, and are perfect. A broader class of graphs, the unipolar graphs can be partitioned into a clique and a cluster graph , a disjoint union of cliques. These include also the bipartite graphs, for which the cluster graph is just a single clique. The unipolar graphs and their complements together form

1598-422: A partially ordered set has the set elements as its vertices, with an edge connecting any two comparable elements. Its complement is called an incomparability graph . Different partial orders may have the same comparability graph; for instance, reversing all comparisons changes the order but not the graph. Finite comparability graphs (and their complementary incomparability graphs) are always perfect. A clique, in

1692-408: A partition of the vertices of the graph into a sequence of sets; initially this sequence consists of a single set with all vertices. The algorithm repeatedly chooses a vertex v from the earliest set in the sequence that contains previously unchosen vertices, and splits each set S of the sequence into two smaller subsets, the first consisting of the neighbors of v in S and the second consisting of

1786-456: A perfect graph G {\displaystyle G} is also perfect implies that, in G {\displaystyle G} itself, the independence number (the size of its maximum independent set ), equals its clique cover number (the fewest number of cliques needed in a clique cover). More strongly, the same thing is true in every induced subgraph of the complement graph. This provides an alternative and equivalent definition of

1880-427: A perfect graph. This matrix has a column for each vertex of the graph, and a row for each maximal clique , with a coefficient that is one in the columns of vertices that belong to the clique and zero in the remaining columns. The integral linear programs encoded by this matrix seek the maximum-weight independent set of the given graph, with weights given by the vector c {\displaystyle c} . For

1974-444: A permutation graph is another permutation graph, for the reverse of the given permutation. Therefore, as well as being incomparability graphs, permutation graphs are comparability graphs. In fact, the permutation graphs are exactly the graphs that are both comparability and incomparability graphs. A clique, in a permutation graph, is a subsequence of elements that appear in increasing order in the given permutation, and an independent set

SECTION 20

#1733086135067

2068-404: A separator, depending on whether the tree is centered or bicentered . As opposed to these examples, not all vertex separators are balanced , but that property is most useful for applications in computer science, such as the planar separator theorem . Let S be an ( a , b ) -separator, that is, a vertex subset that separates two nonadjacent vertices a and b . Then S is a minimal (

2162-503: A simple equivalent of Kőnig's theorem , a much earlier result relating matchings and vertex covers in bipartite graphs. The first formulation of the concept of perfect graphs more generally was in a 1961 paper by Claude Berge , in German, and the first use of the phrase "perfect graph" appears to be in a 1963 paper of Berge. In these works he unified Gallai's result with several similar results by defining perfect graphs, and he conjectured both

2256-473: A very big difference in the computational complexity of these problems: linear programming can be solved in polynomial time , but integer programming is NP-hard . When the same given values A {\displaystyle A} , b {\displaystyle b} , and c {\displaystyle c} are used to define both a linear program and an integer program, they commonly have different optimal solutions. The linear program

2350-445: Is NP-complete whereas the probe graph problem on chordal graphs has polynomial-time complexity. The set of all perfect elimination orderings of a chordal graph can be modeled as the basic words of an antimatroid ; Chandran et al. (2003) use this connection to antimatroids as part of an algorithm for efficiently listing all perfect elimination orderings of a given chordal graph. Another application of perfect elimination orderings

2444-470: Is windmill graphs , where the common vertex is the same for every pair of cliques. Strongly chordal graphs are graphs that are chordal and contain no n -sun (for n ≥ 3 ) as an induced subgraph. Here an n -sun is an n -vertex chordal graph G together with a collection of n degree-two vertices, adjacent to the edges of a Hamiltonian cycle in  G . K -trees are chordal graphs in which all maximal cliques and all maximal clique separators have

2538-399: Is a vertex separator (or vertex cut , separating set ) for nonadjacent vertices a and b if the removal of S from the graph separates a and b into distinct connected components . Consider a grid graph with r rows and c columns; the total number n of vertices is r × c . For instance, in the illustration, r = 5 , c = 8 , and n = 40 . If r is odd, there

2632-446: Is a chain in the order and a clique in the graph, while { C , D } {\displaystyle \{C,D\}} is an antichain in the order and an independent set in the graph. Thus, a coloring of a comparability graph is a partition of its elements into antichains, and a clique cover is a partition of its elements into chains. Dilworth's theorem , in the theory of partial orders, states that for every finite partial order,

2726-421: Is a clique, and there are no edges from A to B . That is, they are the graphs that have a recursive decomposition by clique separators into smaller subgraphs. For this reason, chordal graphs have also sometimes been called decomposable graphs . An alternative characterization of chordal graphs, due to Gavril (1974) , involves trees and their subtrees. From a collection of subtrees of a tree, one can define

2820-466: Is a clique; Dirac used this characterization to prove that chordal graphs are perfect . The family of chordal graphs may be defined inductively as the graphs whose vertices can be divided into three nonempty subsets A , S , and B , such that ⁠ A ∪ S {\displaystyle A\cup S} ⁠ and ⁠ S ∪ B {\displaystyle S\cup B} ⁠ both form chordal induced subgraphs , S

2914-406: Is a comparability graph. Thus, Kőnig's theorem can be seen as a special case of Dilworth's theorem, connected through the theory of perfect graphs. A permutation graph is defined from a permutation on a totally ordered sequence of elements (conventionally, the integers from 1 {\displaystyle 1} to n {\displaystyle n} ), which form the vertices of

Chordal graph - Misplaced Pages Continue

3008-448: Is a single central row, and otherwise there are two rows equally close to the center; similarly, if c is odd, there is a single central column, and otherwise there are two columns equally close to the center. Choosing S to be any of these central rows or columns, and removing S from the graph, partitions the graph into two smaller connected subgraphs A and B , each of which has at most n ⁄ 2 vertices. If r ≤ c (as in

3102-590: Is a subsequence of elements that appear in decreasing order. In any perfect graph, the product of the clique number and independence number are at least the number of vertices; the special case of this inequality for permutation graphs is the Erdős–Szekeres theorem . The interval graphs are the incomparability graphs of interval orders , orderings defined by sets of intervals on the real line with x ≤ y {\displaystyle x\leq y} whenever interval x {\displaystyle x}

3196-436: Is an arbitrary graph, a chordal completion of G (or minimum fill-in ) is a chordal graph that contains G as a subgraph. The parameterized version of minimum fill-in is fixed parameter tractable , and moreover, is solvable in parameterized subexponential time. The treewidth of G is one less than the number of vertices in a maximum clique of a chordal completion chosen to minimize this clique size. The k -trees are

3290-623: Is another theorem of Dénes Kőnig . In arbitrary simple graphs, they can differ by one; this is Vizing's theorem . The underlying graph G {\displaystyle G} of a perfect line graph L ( G ) {\displaystyle L(G)} is a line perfect graph . These are the graphs whose biconnected components are bipartite graphs, the complete graph K 4 {\displaystyle K_{4}} , and triangular books , sets of triangles sharing an edge. These components are perfect, and their combination preserves perfection, so every line perfect graph

3384-464: Is called an integral linear program if an optimal solution to the integer program is also optimal for the linear program. (Otherwise, the ratio between the two solution values is called the integrality gap , and is important in analyzing approximation algorithms for the integer program.) Perfect graphs may be used to characterize the (0, 1) matrices A {\displaystyle A} (that is, matrices where all coefficients are 0 or 1) with

3478-406: Is complementary to a minimum vertex cover , a set of vertices that touches all edges. A minimum clique cover consists of a maximum matching (as many disjoint edges as possible) together with one-vertex cliques for all remaining vertices, and its size is the number of vertices minus the number of matching edges. Therefore, this equality can be expressed equivalently as an equality between the size of

3572-431: Is completely to the left of interval y {\displaystyle y} . In the corresponding interval graph, there is an edge from x {\displaystyle x} to y {\displaystyle y} whenever the two intervals have a point in common. Coloring these graphs can be used to model problems of assigning resources to tasks (such as classrooms to classes) with intervals describing

3666-428: Is complicated and has a high polynomial exponent. More efficient combinatorial algorithms are known for many special cases. This method can also be generalized to find the maximum weight of a clique, in a weighted graph, instead of the clique number. A maximum or maximum weight clique itself, and an optimal coloring of the graph, can also be found by these methods, and a maximum independent set can be found by applying

3760-453: Is defined by the property that between every two vertices, all induced paths have equal parity: either they are all even in length, or they are all odd in length. These include the distance-hereditary graphs, in which all induced paths between two vertices have the same length, and bipartite graphs, for which all paths (not just induced paths) between any two vertices have equal parity. Parity graphs are Meyniel graphs, and therefore perfect: if

3854-423: Is finding a maximum clique of a chordal graph in polynomial-time, while the same problem for general graphs is NP-complete . More generally, a chordal graph can have only linearly many maximal cliques , while non-chordal graphs may have exponentially many. This implies that the class of chordal graphs has few cliques . To list all maximal cliques of a chordal graph, simply find a perfect elimination ordering, form

Chordal graph - Misplaced Pages Continue

3948-486: Is given as a matrix , and b {\displaystyle b} and c {\displaystyle c} are given as two vectors. Although linear programs and integer programs are specified in this same way, they differ in that, in a linear program, the solution vector x {\displaystyle x} is allowed to have arbitrary real numbers as its coefficients, whereas in an integer program these unknown coefficients must be integers. This makes

4042-404: Is nested or disjoint produce trivially perfect graphs , the comparability graphs of ordered trees . In them, the independence number equals the number of maximal cliques . A split graph is a graph that can be partitioned into a clique and an independent set. It can be colored by assigning a separate color to each vertex of a maximal clique, and then coloring each remaining vertex the same as

4136-404: Is not a generalized split graph, is unipolar or co-unipolar but not both, or is both unipolar and co-unipolar. Several families of perfect graphs can be characterized by an incremental construction in which the graphs in the family are built up by adding one vertex at a time, according to certain rules, which guarantee that after each vertex is added the graph remains perfect. If the vertices of

4230-435: Is not perfect: its clique number is two, but its chromatic number is three. By the perfect graph theorem, the complement of an odd cycle of length greater than three is also not perfect. The complement of a length-5 cycle is another length-5 cycle, but for larger odd lengths the complement is not a cycle; it is called an anticycle . The strong perfect graph theorem asserts that these are the only forbidden induced subgraphs for

4324-476: Is perfect. The bipartite graphs, their complements, and the line graphs of bipartite graphs and their complements form four basic classes of perfect graphs that play a key role in the proof of the strong perfect graph theorem. According to the structural decomposition of perfect graphs used as part of this proof, every perfect graph that is not already in one of these four classes can be decomposed by partitioning its vertices into subsets, in one of four ways, called

4418-404: Is perfect. These two theorems are equivalent via the perfect graph theorem, but Mirsky's theorem is easier to prove directly than Dilworth's theorem: if each element is labeled by the size of the largest chain in which it is maximal, then the subsets with equal labels form a partition into antichains, with the number of antichains equal to the size of the largest chain overall. Every bipartite graph

4512-406: Is simply x , so x divides the polynomial, as it should.) Clearly, this computation depends on chordality. In any graph, a vertex separator is a set of vertices the removal of which leaves the remaining graph disconnected; a separator is minimal if it has no proper subset that is also a separator. According to a theorem of Dirac (1961) , chordal graphs are graphs in which each minimal separator

4606-455: Is the half-angle of this cone. Despite this complicated definition, an accurate numerical value of the Lovász number can be computed using semidefinite programming , and for any graph the Lovász number is sandwiched between the chromatic number and clique number. Because these two numbers equal each other in perfect graphs, they also equal the Lovász number. Thus, they can be computed by approximating

4700-412: Is their recognition, the problem of testing whether a given graph is perfect. For many years the complexity of recognizing Berge graphs and perfect graphs were considered separately (as they were not yet known to be equivalent) and both remained open. They were both known to be in co-NP ; for Berge graphs, this follows from the definition, while for perfect graphs it follows from the characterization using

4794-553: The Lovász number of these graphs. The Lovász number of any graph can be determined by labeling its vertices by high dimensional unit vectors , so that each two non-adjacent vertices have perpendicular labels, and so that all of the vectors lie in a cone with as small an opening angle as possible. Then, the Lovász number is 1 / cos 2 ⁡ θ {\displaystyle 1/\cos ^{2}\theta } , where θ {\displaystyle \theta }

SECTION 50

#1733086135067

4888-585: The Mathematical Optimization Society and American Mathematical Society , for his work on generalizations of the theory of perfect graphs to logical matrices . The conjectured strong perfect graph theorem became the focus of research in the theory of perfect graphs for many years, until its proof was announced in 2002 by Maria Chudnovsky , Neil Robertson , Paul Seymour , and Robin Thomas , and published by them in 2006. This work won its authors

4982-542: The chromatic number equals the size of the maximum clique , both in the graph itself and in every induced subgraph . In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices. The perfect graphs include many important families of graphs and serve to unify results relating colorings and cliques in those families. For instance, in all perfect graphs,

5076-401: The complement graph of a perfect graph is itself perfect. The complement graph has an edge between two vertices if and only if the given graph does not. A clique, in the complement graph, corresponds to an independent set in the given. A coloring of the complement graph corresponds to a clique cover , a partition of the vertices of the given graph into cliques. The fact that the complement of

5170-520: The complements of chordal graphs. Bender, Richmond & Wormald (1985) showed that, in the limit as n goes to infinity, the fraction of n -vertex chordal graphs that are split approaches one. Ptolemaic graphs are graphs that are both chordal and distance hereditary . Quasi-threshold graphs are a subclass of Ptolemaic graphs that are both chordal and cographs . Block graphs are another subclass of Ptolemaic graphs in which every two maximal cliques have at most one vertex in common. A special type

5264-454: The domination perfect graphs are defined as graphs in which, in every induced subgraph, the smallest dominating set (a set of vertices adjacent to all remaining vertices) equals the size of the smallest independent set that is a dominating set. These include, for instance, the claw-free graphs . Vertex separator In graph theory , a vertex subset ⁠ S ⊂ V {\displaystyle S\subset V} ⁠

5358-463: The graph coloring problem , maximum clique problem , and maximum independent set problem can all be solved in polynomial time , despite their greater complexity for non-perfect graphs. In addition, several important minimax theorems in combinatorics , including Dilworth's theorem and Mirsky's theorem on partially ordered sets , Kőnig's theorem on matchings , and the Erdős–Szekeres theorem on monotonic sequences, can be expressed in terms of

5452-404: The 2009 Fulkerson Prize. The perfect graph theorem has a short proof, but the proof of the strong perfect graph theorem is long and technical, based on a deep structural decomposition of Berge graphs. Related decomposition techniques have also borne fruit in the study of other graph classes, and in particular for the claw-free graphs . The symmetric characterization of perfect graphs in terms of

5546-412: The Lovász number accurately enough and rounding the result to the nearest integer. The solution method for semidefinite programs, used by this algorithm, is based on the ellipsoid method for linear programming . It leads to a polynomial time algorithm for computing the chromatic number and clique number in perfect graphs. However, solving these problems using the Lovász number and the ellipsoid method

5640-756: The chordal graph. Chordal graphs are perfectly orderable : an optimal coloring may be obtained by applying a greedy coloring algorithm to the vertices in the reverse of a perfect elimination ordering. The chromatic polynomial of a chordal graph is easy to compute. Find a perfect elimination ordering v 1 , v 2 , …, v n . Let N i equal the number of neighbors of v i that come after v i in that ordering. For instance, N n = 0 . The chromatic polynomial equals ( x − N 1 ) ( x − N 2 ) ⋯ ( x − N n ) . {\displaystyle (x-N_{1})(x-N_{2})\cdots (x-N_{n}).} (The last factor

5734-419: The chromatic number and clique number both equal two. Their induced subgraphs remain bipartite, so bipartite graphs are perfect. Other important families of graphs are bipartite, and therefore also perfect, including for instance the trees and median graphs . By the perfect graph theorem, maximum independent sets in bipartite graphs have the same size as their minimum clique covers. The maximum independent set

SECTION 60

#1733086135067

5828-534: The chromatic number is three for the 7-cycle and four for the other graph shown. The vertices of any clique must have different colors, so the chromatic number is always greater than or equal to the clique number. For some graphs, they are equal; for others, such as the ones shown, they are unequal. The perfect graphs are defined as the graphs for which these two numbers are equal, not just in the graph itself, but in every induced subgraph obtained by deleting some of its vertices. The perfect graph theorem asserts that

5922-421: The class of generalized split graphs . Almost all perfect graphs are generalized split graphs, in the sense that the fraction of perfect n {\displaystyle n} -vertex graphs that are generalized split graphs goes to one in the limit as n {\displaystyle n} grows arbitrarily large. Other limiting properties of almost all perfect graphs can be determined by studying

6016-535: The complements of tolerance graphs , a generalization of interval graphs. The strongly perfect graphs are graphs in which, in every induced subgraph, there exists an independent set that intersects all maximal cliques . In the Meyniel graphs or very strongly perfect graphs , every vertex belongs to such an independent set. The Meyniel graphs can also be characterized as the graphs in which every odd cycle of length five or more has at least two chords. A parity graph

6110-422: The following property: if b {\displaystyle b} is the all-ones vector , then for all choices of c {\displaystyle c} the resulting linear program is integral. As Václav Chvátal proved, every matrix A {\displaystyle A} with this property is (up to removal of irrelevant "dominated" rows) the maximal clique versus vertex incidence matrix of

6204-403: The generalized split graphs. In this way, it has been shown that almost all perfect graphs contain a Hamiltonian cycle . If H {\displaystyle H} is an arbitrary graph, the limiting probability that H {\displaystyle H} occurs as an induced subgraph of a large random perfect graph is 0, 1/2, or 1, respectively as H {\displaystyle H}

6298-423: The graph, with facets corresponding to the maximal cliques in the graph. The perfect graphs are the only graphs for which the two polytopes defined in this way from independent sets and from maximal cliques coincide. In all perfect graphs, the graph coloring problem , maximum clique problem , and maximum independent set problem can all be solved in polynomial time . The algorithm for the general case involves

6392-446: The graph. The edges of a permutation graph connect pairs of elements whose ordering is reversed by the given permutation. These are naturally incomparability graphs, for a partial order in which x ≤ y {\displaystyle x\leq y} whenever x {\displaystyle x} occurs before y {\displaystyle y} in both the given sequence and its permutation. The complement of

6486-418: The graphs for which the product of the clique number and independence number is greater than or equal to the number of vertices, and for which the same is true for all induced subgraphs. Because the statement of this characterization remains invariant under complementation of graphs, it implies the perfect graph theorem. One direction of this characterization follows easily from the original definition of perfect:

6580-442: The graphs that are both odd-hole-free and even-hole-free (see holes in graph theory). Every chordal graph is a strangulated graph , a graph in which every peripheral cycle is a triangle, because peripheral cycles are a special case of induced cycles. Strangulated graphs are graphs that can be formed by clique-sums of chordal graphs and maximal planar graphs. Therefore, strangulated graphs include maximal planar graphs . If G

6674-406: The graphs to which no additional edges can be added without increasing their treewidth to a number larger than  k . Therefore, the k -trees are their own chordal completions, and form a subclass of the chordal graphs. Chordal completions can also be used to characterize several other related classes of graphs. Perfect graph In graph theory , a perfect graph is a graph in which

6768-472: The graphs with no odd hole and no odd antihole) were called Berge graphs . The perfect graph theorem was proven by László Lovász in 1972, who in the same year proved the stronger inequality between the number of vertices and the product of the clique number and independence number, without benefit of the strong perfect graph theorem. In 1991, Alfred Lehman won the Fulkerson Prize , sponsored jointly by

6862-465: The illustration), then choosing a central column will give a separator S with r ≤ n {\displaystyle r\leq {\sqrt {n}}} vertices, and similarly if c ≤ r then choosing a central row will give a separator with at most n {\displaystyle {\sqrt {n}}} vertices. Thus, every grid graph has a separator S of size at most n , {\displaystyle {\sqrt {n}},}

6956-461: The largest clique in the graph; the tree decomposition of any graph G can be viewed in this way as a representation of G as a subgraph of a chordal graph. The tree decomposition of a graph is also the junction tree of the junction tree algorithm . Interval graphs are the intersection graphs of subtrees of path graphs , a special case of trees. Therefore, they are a subfamily of chordal graphs. Split graphs are graphs that are both chordal and

7050-420: The line graphs of bipartite graphs are perfect. Examples include the rook's graphs , the line graphs of complete bipartite graphs . Every line graph of a bipartite graph is an induced subgraph of a rook's graph. Because line graphs of bipartite graphs are perfect, their clique number equals their chromatic number. The clique number of the line graph of a bipartite graph is the maximum degree of any vertex of

7144-707: The maximum matching and the minimum vertex cover in bipartite graphs, the usual formulation of Kőnig's theorem . A matching, in any graph G {\displaystyle G} , is the same thing as an independent set in the line graph L ( G ) {\displaystyle L(G)} , a graph that has a vertex for each edge in G {\displaystyle G} and an edge between two vertices in L ( G ) {\displaystyle L(G)} for each pair of edges in G {\displaystyle G} that share an endpoint. Line graphs have two kinds of cliques: sets of edges in G {\displaystyle G} with

7238-410: The minimal separators: Lemma. A vertex separator S in G is minimal if and only if the graph G – S , obtained by removing S from G , has two connected components C 1 and C 2 such that each vertex in S is both adjacent to some vertex in C 1 and to some vertex in C 2 . The minimal ( a , b ) -separators also form an algebraic structure : For two fixed vertices

7332-462: The non-neighbors. When this splitting process has been performed for all vertices, the sequence of sets has one vertex per set, in the reverse of a perfect elimination ordering. Since both this lexicographic breadth first search process and the process of testing whether an ordering is a perfect elimination ordering can be performed in linear time , it is possible to recognize chordal graphs in linear time. The graph sandwich problem on chordal graphs

7426-433: The number of vertices in any graph equals the sum of the sizes of the color classes in an optimal coloring, and is less than or equal to the number of colors multiplied by the independence number. In a perfect graph, the number of colors equals the clique number, and can be replaced by the clique number in this inequality. The other direction can be proved directly, but it also follows from the strong perfect graph theorem: if

7520-462: The perfect graph theorem and the strong perfect graph theorem. In formulating these concepts, Berge was motivated by the concept of the Shannon capacity of a graph , by the fact that for (co-)perfect graphs it equals the independence number, and by the search for minimal examples of graphs for which this is not the case. Until the strong perfect graph theorem was proven, the graphs described by it (that is,

7614-513: The perfect graphs: a graph is perfect if and only if its induced subgraphs include neither an odd cycle nor an odd anticycle of five or more vertices. In this context, induced cycles that are not triangles are called "holes", and their complements are called "antiholes", so the strong perfect graph theorem can be stated more succinctly: a graph is perfect if and only if it has neither an odd hole nor an odd antihole. These results can be combined in another characterization of perfect graphs: they are

7708-406: The perfect graphs: they are the graphs for which, in each induced subgraph, the independence number equals the clique cover number. The strong perfect graph theorem gives a different way of defining perfect graphs, by their structure instead of by their properties. It is based on the existence of cycle graphs and their complements within a given graph. A cycle of odd length, greater than three,

7802-415: The perfection of comparability graphs , associated with Dilworth's theorem and Mirsky's theorem on chains and antichains in partially ordered sets . Other important classes of graphs, defined by having a structure related to the holes and antiholes of the strong perfect graph theorem, include the chordal graphs , Meyniel graphs , and their subclasses. In bipartite graphs (with at least one edge)

7896-456: The perfection of certain associated graphs. The perfect graph theorem states that the complement graph of a perfect graph is also perfect. The strong perfect graph theorem characterizes the perfect graphs in terms of certain forbidden induced subgraphs , leading to a polynomial time algorithm for testing whether a graph is perfect. A clique in an undirected graph is a subset of its vertices that are all adjacent to each other, such as

7990-530: The product of clique number and independence number was originally suggested by Hajnal and proven by Lovász. Many well-studied families of graphs are perfect, and in many cases the fact that these graphs are perfect corresponds to a minimax theorem for some kinds of combinatorial structure defined by these graphs. Examples of this phenomenon include the perfection of bipartite graphs and their line graphs , associated with Kőnig's theorem relating maximum matchings and vertex covers in bipartite graphs, and

8084-405: The product of the clique number and independence number. After the strong perfect graph theorem was proved, Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković discovered a polynomial time algorithm for testing the existence of odd holes or anti-holes. By the strong perfect graph theorem, this can be used to test whether a given graph is perfect, in polynomial time. Generalizing the perfect graphs,

8178-425: The removal of which partitions it into two connected components, each of size at most n ⁄ 2 . To give another class of examples, every free tree T has a separator S consisting of a single vertex, the removal of which partitions T into two or more connected components, each of size at most n ⁄ 2 . More precisely, there is always exactly one or exactly two vertices, which amount to such

8272-407: The same approach to the complement of the graph. For instance, a maximum clique can be found by the following algorithm: The algorithm for finding an optimal coloring is more complicated, and depends on the duality theory of linear programs, using this clique-finding algorithm as a separation oracle . Beyond solving these problems, another important computational problem concerning perfect graphs

8366-446: The same size. Apollonian networks are chordal maximal planar graphs , or equivalently planar 3-trees. Maximal outerplanar graphs are a subclass of 2-trees, and therefore are also chordal. Chordal graphs are a subclass of the well known perfect graphs . Other superclasses of chordal graphs include weakly chordal graphs, cop-win graphs , odd-hole-free graphs, even-hole-free graphs , and Meyniel graphs . Chordal graphs are precisely

8460-474: The scheduled time of each task. Both interval graphs and permutation graphs are generalized by the trapezoid graphs . Systems of intervals in which no two are nested produce a more restricted class of graphs, the indifference graphs , the incomparability graphs of semiorders . These have been used to model human preferences under the assumption that, when items have utilities that are very close to each other, they will be incomparable. Intervals where every pair

8554-439: The size of the largest antichain equals the minimum number of chains into which the elements can be partitioned. In the language of graphs, this can be stated as: every finite comparability graph is perfect. Similarly, Mirsky's theorem states that for every finite partial order, the size of the largest chain equals the minimum number of antichains into which the elements can be partitioned, or that every finite incomparability graph

8648-476: The subsets of vertices connected by heavy edges in the illustration. The clique number is the number of vertices in the largest clique: two in the illustrated seven-vertex cycle, and three in the other graph shown. A graph coloring assigns a color to each vertex so that each two adjacent vertices have different colors, also shown in the illustration. The chromatic number of a graph is the minimum number of colors in any coloring. The colorings shown are optimal, so

8742-446: The underlying bipartite graph. The chromatic number of the line graph of a bipartite graph is the chromatic index of the underlying bipartite graph, the minimum number of colors needed to color the edges so that touching edges have different colors. Each color class forms a matching, and the chromatic index is the minimum number of matchings needed to cover all edges. The equality of maximum degree and chromatic index, in bipartite graphs,

8836-506: The vertices of a comparability graph are colored in the order of a linear extension of its underlying partial order, the resulting coloring will be optimal. This property is generalized in the family of perfectly orderable graphs , the graphs for which there exists an ordering that, when restricted to any induced subgraph, causes greedy coloring to be optimal. The cographs are exactly the graphs for which all vertex orderings have this property. Another subclass of perfectly orderable graphs are

#66933