In discrete mathematics, a convex space is an ordered pair (V,M) where M is a family of subsets of a finite set V , such that: ∅ ∈M, V ∈M, andMis closed under intersection. The elements of M are called convex sets. For a set S ⊆ V , the convex hull of S is the smallest convex set that contains S. A point x of a convex set X is an extreme point of X if X\{x} is also convex. A convex space (V,M) with the property that every convex set is the convex hull of its extreme points is called a convex geometry. A graph G has a P-elimination ordering if an ordering v1, v2, ..., vn of the vertices exists such that vi has property P in the graph induced by vertices vi, vi+1, ..., vn for all i = 1, 2, ...,n. Farber and Jamison [18] showed that for a convex geometry (V,M), X ∈Mif and only if there is an ordering v1, v2, ..., vk of the points of V − X such that vi is an extreme point of {vi, vi+1, ..., vk}∪ X for each i = 1, 2, ...,k. With these concepts in mind, this thesis surveys the literature and summarizes results regarding graph convexities and elimination orderings. These results include classifying graphs for which different types of convexities give convex geometries, and classifying graphs for which different vertex ordering algorithms result in a P-elimination ordering, for P the characteristic property of the extreme points of the convexity. We consider the geodesic, monophonic, m3, 3-Steiner and 3-monophonic convexities, and the vertex ordering algorithms LexBFS, MCS, MEC and MCC. By considering LexDFS, a recently introduced vertex ordering algorithm of Corneil and Krueger [11], we obtain new results: these are characterizations of graphs for which all LexDFS orderings of all induced subgraphs are P-elimination orderings, for every characteristic property P of the extreme vertices for the convexities studied in this thesis. / Graduate / 0405 / rachela@uvic.ca

In discrete mathematics, a convex space is an ordered pair (V,M) where M is a family of subsets of a finite set V , such that: ∅ ∈M, V ∈M, andMis closed under intersection. The elements of M are called convex sets. For a set S ⊆ V , the convex hull of S is the smallest convex set that contains S. A point x of a convex set X is an extreme point of X if X\{x} is also convex. A convex space (V,M) with the property that every convex set is the convex hull of its extreme points is called a convex geometry. A graph G has a P-elimination ordering if an ordering v1, v2, ..., vn of the vertices exists such that vi has property P in the graph induced by vertices vi, vi+1, ..., vn for all i = 1, 2, ...,n. Farber and Jamison [18] showed that for a convex geometry (V,M), X ∈Mif and only if there is an ordering v1, v2, ..., vk of the points of V − X such that vi is an extreme point of {vi, vi+1, ..., vk}∪ X for each i = 1, 2, ...,k. With these concepts in mind, this thesis surveys the literature and summarizes results regarding graph convexities and elimination orderings. These results include classifying graphs for which different types of convexities give convex geometries, and classifying graphs for which different vertex ordering algorithms result in a P-elimination ordering, for P the characteristic property of the extreme points of the convexity. We consider the geodesic, monophonic, m3, 3-Steiner and 3-monophonic convexities, and the vertex ordering algorithms LexBFS, MCS, MEC and MCC. By considering LexDFS, a recently introduced vertex ordering algorithm of Corneil and Krueger [11], we obtain new results: these are characterizations of graphs for which all LexDFS orderings of all induced subgraphs are P-elimination orderings, for every characteristic property P of the extreme vertices for the convexities studied in this thesis. / Graduate / 0405 / rachela@uvic.ca

This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs. We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in: + some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs); + some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs); + some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs. Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes. We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem. We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs. We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered. Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.

This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs. We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in: + some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs); + some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs); + some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs. Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes. We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem. We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs. We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered. Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.