Suppose G is a graph with n vertices and m edges. Let n¡¬ be the maximum number of vertices in an induced bipartite subgraph of G and let m¡¬ be the maximum number of edges in a spanning bipartite subgraph of G. Then b(G) = m¡¬/m is called the bipartite density of G, and b∗(G) = n¡¬/n is called the bipartite ratio of G. It is proved in [18] that if G is a 2-connected triangle-free subcubic graph, then apart from seven exceptional graphs, we have b(G) ≥ 17/21. If G is a 2-connected triangle-free subcubic graph, then b∗(G) ≥ 5/7 provided that G is not the Petersen graph and not the dodecahedron. These two results are consequences of a more technical result which is proved by induction: If G is a 2-connected triangle-free subcubic graph with minimum degree 2, then G has an induced bipartite subgraph H with |V (H)| ≥ (5n3 + 6n2 + ǫ(G))/7, where ni = ni(G) are the number of degree i vertices of G, and ǫ(G) ∈ {−2,−1, 0, 1}. To determine ǫ(G), four classes of graphs G1, G2, G3 and F-cycles are onstructed. For G ∈ Gi, we have ǫ(G) = −3 + i and for an F-cycle G, we have ǫ(G) = 0. Otherwise, ǫ(G) = 1. To construct these graph classes, eleven graph operations are used. This thesis studies the structural property of graphs in G1, G2, G3. First of all, a computer algorithm is used to generate all the graphs in Gi for i = 1, 2, 3. Let P be the set of 2-edge connected subcubic triangle-free planar graphs with minimum degree 2. Let G¡¬ 1 be the set of graphs in P with all faces of degree 5, G¡¬2 the set of graphs in P with all faces of degree 5 except that one face has degree 7, and G¡¬3 the set of graphs in P with all faces of degree 5 except that either two faces are of degree 7 or one face is of degree 9. By checking the graphs generated by the computer algorithm, it is easy to see that Gi ⊆ G¡¬i for i = 1, 2, 3. The main results of this thesis are that for i = 1, 2, Gi = G¡¬i and G¡¬3 = G3 ¡åR, where R is a set of nine F-cycles.

A proper edge coloring of G =(V,E)is a map c : E → C (where C is the set of available colors ) with c(e) ≠ c(ƒ) for any adjacent edges e,f. The minimum number of colors needed to properly color the edges of G, is called the chromatic index of Gand is denoted by χ(G). A proper edge coloring c is called acyclic if there are no bichromatic cycles in the graph. In other words an edge coloring is acyclic if the union of any two color classes induces a set of paths (i.e., linear forest) in G. The acyclic edge chromatic number (also called acyclic chromatic index), denoted by a’(G), is the minimum number of colors required to acyclically edge color G. The primary motivation for this thesis is the following conjecture by Alon, Sudakov and Zaks [7] (and independently by Fiamcik [22]): Acyclic Edge Coloring Conjecture: For any graph G, a’ (G) ≤ Δ(G)+2. The following are the main results of the thesis: 1 From a result of Burnstein [16], it follows that any subcubic graph can be acyclically edge colored using at most 5 colors. Skulrattankulchai [38] gave a polynomial time algorithm to color a subcubic graph using Δ + 2 = 5 colors. We proved that any non-regular subcubic graph can be acyclically colored using only 4 colors. This result is tight. This also implies that the fifth color, when needed is required only for one edge. 2 Let G be a connected graph on n vertices, m ≤ 2n - 1 edges and maximum degree Δ ≤ 4, then a’ (G) ≤ 6. This implies that graph of maximum degree 4 are acyclically edge colorable using at most 7 colors. 3 The earliest result on acyclic edge coloring of 2-degenerate graphs was by Caro and Roditty [17], where they proved that a’ (G) ≤ Δ + k - 1, where k is the maximum edge connectivity, defined as k = maxu,vε V(G)λ(u,v), where λ(u,v)is the edge-connectivity of the pair u,v. Note that here k can be as high as Δ. Muthu,Narayanan and Subramanian [34] proved that a’ (G) ≤ Δ + 1for outerplanar graphs which are a subclass of 2-degenerate graphs and posed the problem of proving the conjecture for 2-degenerate graphs as an open problem. In fact they have also derived an upper bound of Δ+1 for series-parallel graphs [35], which is a slightly bigger subclass of 2-degenerate graphs. We proved that 2-degenerate graphs are Δ+1colorable. 1 Fiedorowicz, Hauszczak and Narayanan [24] gave an upper bound of 2Δ+29 for planar graphs. Independently Hou, Wu, GuiZhen Liu and Bin Liu [29] gave an upper bound of max(2Δ - 2,Δ+ 22). We improve this upper bound to Δ+12, which is the best known bound at present. 2 Fiedorowicz, Hauszczak and Narayanan [24] gave an upper bound of Δ+6for triangle free planar graphs. We improve the bound to Δ+3, which is the best known bound at present. 3 We have also worked on lower bounds. Alon et.al. [7], along with the acyclic edge coloring conjecture, also made an auxiliary conjecture stating that Complete graphs of 2n vertices are the only class of regular graphs which require Δ+2colors. We disproved this conjecture by showing infinite classes of regular graphs other than Complete Graphs which require Δ+2colors. Apart from the above mentioned results, this thesis also contributes to the acyclic edge coloring literature by introducing new techniques like Recoloring, Color Exchange (exchanging colors of adjacent edges), circular shifting of colors on adjacent edges (derangement of colors). These techniques turn out to be very useful in proving upper bounds on the acyclic edge chromatic number.

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.