Search

International audience; Truemper configurations are four types of graphs (namely thetas, wheels, prisms and pyramids) that play an important role in the proof of several decomposition theorems for hereditary graph classes. In this paper, we prove two structure theorems: one for graphs with no thetas, wheels and prisms as induced subgraphs, and one for graphs with no thetas, wheels and pyramids as induced subgraphs. A consequence is a polynomial time recognition algorithms for these two classes. In Part II of this series we generalize these results to graphs with no thetas and wheels as induced subgraphs, and in Parts III and IV, using the obtained structure, we solve several optimization problems for these graphs. AMS classification: 05C75

International audience; A hole in a graph is a chordless cycle of length at least 4. A theta is a graph formed by three paths between the same pair of distinct vertices so that the union of any two of the paths induces a hole. A wheel is a graph formed by a hole and a node that has at least 3 neighbors in the hole. In this series of papers we study the class of graphs that do not contain as an induced subgraph a theta nor a wheel. In Part II of the series we prove a decomposition theorem for this class, that uses clique cutsets and 2-joins, and consequently obtain a polynomial time recognition algorithm for the class. In this paper we further use this decomposition theorem to obtain polynomial time algorithms for maximum weight clique, maximum weight stable set and coloring problems. We also show that for a graph $G$ in the class, if its maximum clique size is $\omega$, then its chromatic number is bounded by max$\{\omega,3\}$, and that the class is 3-clique-colorable.

Truemper configurations (thetas, pyramids, prisms, and wheels) have played an important role in the study of complex hereditary graph classes (e.g. the class of perfect graphs and the class of even-hole-free graphs), appearing both as excluded configurations, and as configurations around which graphs can be decomposed. In this paper, we study the structure of graphs that contain (as induced subgraphs) no Truemper configurations other than (possibly) universal wheels and twin wheels. We also study several subclasses of this class. We use our structural results to analyze the complexity of the recognition, maximum weight clique, maximum weight stable set, and optimal vertex coloring problems for these classes. We also obtain polynomial χ-bounding functions for these classes.

International audience; A hole in a graph is a chordless cycle of length at least 4. A theta is a graph formed by three internally vertex-disjoint paths of length at least 2 between the same pair of distinct vertices. A wheel is a graph formed by a hole and a node that has at least 3 neighbors in the hole. In this series of papers we study the class of graphs that do not contain as an induced subgraph a theta nor a wheel. In Part II of the series we prove a decomposition theorem for this class, that uses clique cutsets and 2-joins. In this paper we use this decomposition theorem to solve several problems related to finding induced paths and cycles in our class.

Treewidth is a parameter that emerged from the study of minor closed classes of graphs (i.e. classes closed under vertex and edge deletion, and edge contraction). It in some sense describes the global structure of a graph. Roughly, a graph has treewidth $k$ if it can be decomposed by a sequence of noncrossing cutsets of size at most $k$ into pieces of size at most $k+1$. The study of hereditary graph classes (i.e. those closed under vertex deletion only) reveals a different picture, where cutsets that are not necessarily bounded in size (such as star cutsets, 2-joins and their generalization) are required to decompose the graph into simpler pieces that are structured but not necessarily bounded in size. A number of such decomposition theorems are known for complex hereditary graph classes, including even-hole-free graphs, perfect graphs and others. These theorems do not describe the global structure in the sense that a tree decomposition does, since the cutsets guaranteed by them are far from being noncrossing. They are also of limited use in algorithmic applications. We show that in the case of even-hole-free graphs of bounded degree the cutsets described in the previous paragraph can be partitioned into a bounded number of well-behaved collections. This allows us to prove that even-hole-free graphs with bounded degree have bounded treewidth, resolving a conjecture of Aboulker, Adler, Kim, Sintiari and Trotignon [arXiv:2008.05504]. As a consequence, it follows that many algorithmic problems can be solved in polynomial time for this class, and that even-hole-freeness is testable in the bounded degree graph model of property testing. In fact we prove our results for a larger class of graphs, namely the class of $C_4$-free odd-signable graphs with bounded degree.

A hole in a graph is a chordless cycle of length at least 4. A theta is a graph formed by three paths between the same pair of distinct vertices so that the union of any two of the paths induces a hole. A wheel is a graph formed by a hole and a node that has at least 3 neighbors in the hole. In this paper we obtain a decomposition theorem for the class of graphs that do not contain an induced subgraph isomorphic to a theta or a wheel, i.e. the class of (theta, wheel)-free graphs. The decomposition theorem uses clique cutsets and 2-joins. Clique cutsets are vertex cutsets that work really well in decomposition based algorithms, but are unfortunately not general enough to decompose more complex hereditary graph classes. A 2-join is an edge cutset that appeared in decomposition theorems of several complex classes, such as perfect graphs, even-hole-free graphs and others. In these decomposition theorems 2-joins are used together with vertex cutsets that are more general than clique cutsets, such as star cutsets and their generalizations (which are much harder to use in algorithms). This is a first example of a decomposition theorem that uses just the combination of clique cutsets and 2-joins. This has several consequences. First, we can easily transform our decomposition theorem into a complete structure theorem for (theta, wheel)-free graphs, i.e. we show how every (theta, wheel)-free graph can be built starting from basic graphs that can be explicitly constructed, and gluing them together by prescribed composition operations; and all graphs built this way are (theta, wheel)-free. Such structure theorems are very rare for hereditary graph classes, only a few examples are known. Secondly, we obtain an O ( n 4 m ) -time decomposition based recognition algorithm for (theta, wheel)-free graphs. Finally, in Parts III and IV of this series, we give further applications of our decomposition theorem.

We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the sense that there are graphs with exponentially many minimal separators if only three of the four induced subgraphs are excluded. As a consequence, there is a polynomial time algorithm to solve the maximum weight independent set problem for the class of (theta, pyramid, prism, turtle)-free graphs. Since every prism, theta, and turtle contains an even hole, this also implies a polynomial time algorithm to solve the maximum weight independent set problem for the class of (pyramid, even hole)-free graphs.

In this paper, we study the class of graphs C defined by excluding the following structures as induced subgraphs: theta, pyramid, 1‐wheel, and 3‐wheel. We describe the structure of graphs in C, and we give a polynomial‐time recognition algorithm for this class. We also prove that K₄‐free graphs in C are 4‐colorable. We remark that C includes the class of chordal graphs, as well as the class of line graphs of triangle‐free graphs.

A graph is even-hole-free if it has no induced even cycles of length 4 or more. A cap is a cycle of length at least 5 with exactly one chord and that chord creates a triangle with the cycle. In this paper, we consider (cap, even hole)-free graphs, and more generally, (cap, 4-hole)-free odd-signable graphs. We give an explicit construction of these graphs. We prove that every such graph G has a vertex of degree at most 3 2 ω ( G ) − 1 , and hence χ ( G ) ≤ 3 2 ω ( G ) , where ω ( G ) denotes the size of a largest clique in G and χ ( G ) denotes the chromatic number of G . We give an O ( n m ) algorithm for q -coloring these graphs for fixed q and an O ( n m ) algorithm for maximum weight stable set, where n is the number of vertices and m is the number of edges of the input graph. We also give a polynomial-time algorithm for minimum coloring. Our algorithms are based on our results that triangle-free odd-signable graphs have treewidth at most 5 and thus have clique-width at most 48, and that (cap, 4-hole)-free odd-signable graphs G without clique cutsets have treewidth at most 6 ω ( G ) − 1 and clique-width at most 48.

For a graph G , let β ( G ) = max { δ ( G ′ ) + 1 ∣ G ′ is an induced subgraph of G } . This parameter is an upper bound on the chromatic number of a graph. A graph G is β -perfect if χ ( G ′ ) = β ( G ′ ) for all induced subgraphs G ′ of G . A number of classes have been shown in literature to be β -perfect, but for the class of all β -perfect graphs, the complexity of their recognition and characterization in terms of forbidden induced subgraphs remain open. It is known that minimally β -imperfect graphs cannot have a simplicial extreme, i.e. a vertex whose neighborhood is a clique or of size 2. β -perfection of all the known β -perfect classes of graphs was shown through the existence of simplicial extremes. In this paper we study two classes of β -perfect graphs that do not necessarily have this property. Firstly, we prove that (even hole, twin wheel, cap)-free graphs are β -perfect. This class properly contains chordal graphs, and is the only known generalization of chordal graphs that is shown to be β -perfect. Secondly, we give a complete structural characterization of β -perfect hyperholes (graphs obtained from a hole by a sequence of clique substitutions), which we then use to give a linear-time algorithm to recognize whether a hyperhole is β -perfect. We also obtain a complete list of minimally β -imperfect hyperholes.

Truemper configurations (thetas, pyramids, prisms, and wheels) have played an important role in the study of complex hereditary graph classes (e.g. the class of perfect graphs and the class of even-hole-free graphs), appearing both as excluded configurations, and as configurations around which graphs can be decomposed. In this paper, we study the structure of graphs that contain (as induced subgraphs) no Truemper configurations other than (possibly) universal wheels and twin wheels. We also study several subclasses of this class. We use our structural results to analyze the complexity of the recognition, maximum weight clique, maximum weight stable set, and optimal vertex coloring problems for these classes. We also obtain polynomial χ-bounding functions for these classes.

Jerrum, Sinclair and Vigoda (2004) showed that the permanent of any square matrix can be estimated in polynomial time. This computation can be viewed as approximating the partition function of edge-weighted matchings in a bipartite graph. Equivalently, this may be viewed as approximating the partition function of vertex-weighted independent sets in the line graph of a bipartite graph. Line graphs of bipartite graphs are perfect graphs, and are known to be precisely the class of (claw, diamond, odd hole)-free graphs. So how far does the result of Jerrum, Sinclair and Vigoda extend? We first show that it extends to (claw, odd hole)-free graphs, and then show that it extends to the even larger class of (fork, odd hole)-free graphs. Our techniques are based on graph decompositions, which have been the focus of much recent work in structural graph theory, and on structural results of Chvatal and Sbihi (1988), Maffray and Reed (1999) and Lozin and Milanic (2008)., 25 pages, 11 figures

A ring is a graph $R$ whose vertex set can be partitioned into $k \geq 4$ nonempty sets, $X_1, \dots, X_k$, such that for all $i \in \{1,\dots,k\}$, the set $X_i$ can be ordered as $X_i = \{u_i^1, \dots, u_i^{|X_i|}\}$ so that $X_i \subseteq N_R[u_i^{|X_i|}] \subseteq \dots \subseteq N_R[u_i^1] = X_{i-1} \cup X_i \cup X_{i+1}$. A hyperhole is a ring $R$ such that for all $i \in \{1,\dots,k\}$, $X_i$ is complete to $X_{i-1}\cup X_{i+1}$. In this paper, we prove that the chromatic number of a ring $R$ is equal to the maximum chromatic number of a hyperhole in $R$. Using this result, we give a polynomial-time coloring algorithm for rings. Rings formed one of the basic classes in a decomposition theorem for a class of graphs studied by Boncompagni, Penev, and Vu\v{s}kovi\'c in [Journal of Graph Theory 91 (2019), 192--246]. Using our coloring algorithm for rings, we show that graphs in this larger class can also be colored in polynomial time. Furthermore, we find the optimal $\chi$-bounding function for this larger class of graphs, and we also verify Hadwiger's conjecture for it.

We prove a decomposition theorem for the class of triangle-free graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph. We prove that every graph of girth at least~5 in this class is 3-colorable.

We show that triangle-free graphs that do not contain an induced subgraph isomorphic to a subdivision of K4 are 3-colorable. This proves a conjecture of Trotignon and Vuskovic [J. Graph Theory. 84 (2017), no. 3, pp. 233–248].

The maximum stable set problem is NP-hard, even when restricted to triangle-free graphs. In particular, one cannot expect a polynomial time algorithm deciding if a bull-free graph has a stable set of size k, when k is part of the instance. Our main result in this paper is to show the existence of an FPT algorithm when we parameterize the problem by the solution size k. A polynomial kernel is unlikely to exist for this problem. We show however that our problem has a polynomial size Turing-kernel. More precisely, the hard cases are instances of size O(k 5 ). As a byproduct, if we forbid odd holes in addition to the bull, we show the existence of a polynomial time algorithm for the stable set problem. We also prove that the chromatic number of a bull-free graph is bounded by a function of its clique number and the maximum chromatic number of its triangle-free induced subgraphs. All our results rely on a decomposition theorem of bull-free graphs due to Chudnovsky which is modified here, allowing us to provide extreme decompositions, adapted to our computational purpose.

In Math Program 55(1992), 129–168, Conforti and Rao conjectured that every balanced bipartite graph contains an edge that is not the unique chord of a cycle. We prove this conjecture for balanced bipartite graphs that do not contain a cycle of length 4 (also known as linear balanced bipartite graphs), and for balanced bipartite graphs whose maximum degree is at most 3. We in fact obtain results for more general classes, namely linear balanceable and subcubic balanceable graphs. Additionally, we prove that cubic balanced graphs contain a pair of twins, a result that was conjectured by Morris, Spiga, and Webb in ( Discrete Math 310(2010), 3228–3235).

In this paper we consider the class of simple graphs defined by excluding, as induced subgraphs, even holes (i.e. chordless cycles of even length). These graphs are known as even-hole-free graphs. We prove a decomposition theorem for even-hole-free graphs, that uses star cutsets and 2-joins. This is a significant strengthening of the only other previously known decomposition of even-hole-free graphs, by Conforti, Cornuéjols, Kapoor and Vušković, that uses 2-joins and star, double star and triple star cutsets. It is also analogous to the decomposition of Berge (i.e. perfect) graphs with skew cutsets, 2-joins and their complements, by Chudnovsky, Robertson, Seymour and Thomas. The similarity between even-hole-free graphs and Berge graphs is higher than the similarity between even-hole-free graphs and simply odd-hole-free graphs, since excluding a 4-hole, automatically excludes all antiholes of length at least 6. In a graph that does not contain a 4-hole, a skew cutset reduces to a star cutset, and a 2-join in the complement implies a star cutset, so in a way it was expected that even-hole-free graphs can be decomposed with just the star cutsets and 2-joins. A consequence of this decomposition theorem is a recognition algorithm for even-hole-free graphs that is significantly faster than the previously known ones.

The chromatic number of a triangle-free graph can be arbitrarily large. In this article, we show that if all subdivisions of K2, 3 are also excluded as induced subgraphs, then the chromatic number becomes bounded by 3. We give a structural characterization of this class of graphs, from which we derive an coloring algorithm, where n denotes the number of vertices and m the number of edges of the input graph.

The class of even-hole-free graphs is structurally quite similar to the class of perfect graphs, which was the key initial motivation for their study. The techniques developed in the study of even-hole-free graphs were generalized to other complex hereditary graph classes, and in the case of perfect graphs led to the famous resolution of the Strong Perfect Graph Conjecture and their polynomial time recognition. The class of even-holefree graphs is also of independent interest due to its relationship to ?-perfect graphs. In this survey we describe all the different structural characterizations of even-hole-free graphs, focusing on their algorithmic consequences.

International audience; We provide a general method to prove the existence and compute efficiently elimination orderings in graphs. Our method relies on several tools that were known before, but that were not put together so far: the algorithm LexBFS due to Rose, Tarjan and Lueker, one of its properties discovered by Berry and Bordat, and a local decomposition property of graphs discovered by Maffray, Trotignon and Vu\vskovi\'c. We use this method to prove the existence of elimination orderings in several classes of graphs, and to compute them in linear time. Some of the classes have already been studied, namely even-hole-free graphs, square-theta-free Berge graphs, universally signable graphs and wheel-free graphs. Some other classes are new. It turns out that all the classes that we study in this paper can be defined by excluding some of the so-called Truemper configurations. For several classes of graphs, we obtain directly bounds on the chromatic number, or fast algorithms for the maximum clique problem or the coloring problem.

We present a polynomial-time algorithm for recognizing quasi-Meyniel graphs. A hole is a chordless cycle with at least four vertices. A cap is a cycle with at least 6ve vertices, with a single chord that forms a triangle with two edges of the cycle. A graph G is quasi-Meyniel if it contains no odd hole and for some x ∈ V (G), the chord of every cap in G has x as an endvertex. Our recognition algorithm is based on star cutset decompositions. ? 2001 Elsevier Science B.V. All rights reserved.

In this paper, we survey results and open problems on perfect, ideal and balanced matrices. These matrices arise in connection with the set packing and set covering problems, two integer programming models with a wide range of applications. We concentrate on some of the beautiful polyhedral results that have been obtained in this area in the last 30 years. This survey first appeared in Ricerca Operativa.

A 0, ±1 matrix is balanced if, in every square submatrix with two nonzero entries per row and column, the sum of the entries is a multiple of four. This paper extends the decomposition of balanced 0, 1 matrices obtained by Conforti, Cornuéjols, and Rao (1999, J. Combin. Theory Ser. B77, 292–406) to the class of balanced 0, ±1 matrices. As a consequence, we obtain a polynomial time algorithm for recognizing balanced 0, ±1 matrices.

In 1982 Truemper gave a theorem that characterizes graphs whose edges can be labeled so that all chordless cycles have prescribed parities. The characterization states that this can be done for a graph G if and only if it can be done for all induced subgraphs of G that are of few speci c types, that we will call Truemper con gurations. Truemper was originally motivated by the problem of obtaining a co-NP characterization of bipartite graphs that are signable to be balanced (i.e. bipartite graphs whose node-node incidence matrices are balanceable matrices). The con gurations that Truemper identi ed in his theorem ended up playing a key role in understanding the structure of several seemingly diverse classes of objects, such as regular matroids, balanceable matrices and perfect graphs. In this survey we view all these classes, and more, through the excluded Truemper con gurations, focusing on the algorithmic consequences, trying to understand what structurally enables e cient recognition and optimization algorithms.

Roussel and Rubio proved a lemma which is essential in the proof of the Strong Perfect Graph Theorem. We give a new short proof of the main case of this lemma. In this note, we also give a short proof of Hayward’s decomposition theorem for weakly chordal graphs, relying on a Roussel–Rubio-type lemma. We recall how Roussel–Rubio-type lemmas yield very short proofs of the existence of even pairs in weakly chordal graphs and Meyniel graphs.

International audience; We present an $O(n^5)$ algorithm that computes a maximum stable set of any perfect graph with no balanced skew-partition. We present $O(n^7)$ time algorithm that colors them.

We generalize Hall's condition for the existence of a perfect matching in a bipartite graph, to balanced hypergraphs.

2-joins are edge cutsets that naturally appear in the decomposition of several classes of graphs closed under taking induced subgraphs, such as balanced bipartite graphs, even-hole-free graphs, perfect graphs and claw-free graphs. Their detection is needed in several algorithms, and is the slowest step for some of them. The classical method to detect a 2-join takes $O(n^3m)$ time where $n$ is the number of vertices of the input graph and $m$ the number of its edges. To detect \emph{non-path} 2-joins (special kinds of 2-joins that are needed in all of the known algorithms that use 2-joins), the fastest known method takes time $O(n^4m)$. Here, we give an $O(n^2m)$-time algorithm for both of these problems. A consequence is a speed up of several known algorithms.

We recall several known results about minimally 2-connected graphs, and show that they all follow from a decomposition theorem. Starting from an analogy with critically 2-connected graphs, we give structural characterizations of the classes of graphs that do not contain as a subgraph and as an induced subgraph, a cycle with a node that has at least two neighbors on the cycle. From these characterizations we get polynomial time recognition algorithms for these classes, as well as polynomial time algorithms for vertex-coloring and edge-coloring.

International audience; A 2-join is an edge cutset that naturally appears in decomposition of several classes of graphs closed under taking induced sub-graphs, such as perfect graphs and claw-free graphs. In this paper we construct combinatorial polynomial time algorithms for finding a maximum weighted clique, a maximum weighted stable set and an optimal coloring for a class of perfect graphs decomposable by 2-joins: the class of perfect graphs that do not have a balanced skew partition, a 2-join in the complement, nor a homogeneous pair. The techniques we develop are general enough to be easily applied to finding a maximum weighted stable set for another class of graphs known to be decomposable by 2-joins, namely the class of even-hole-free graphs that do not have a star cutset.We also give a simple class of graphs decomposable by 2-joins into bipartite graphs and line graphs, and for which finding a maximum stable set is NP-hard. This shows that having holes all of the same parity gives essential properties for the use of 2-joins in computing stable sets

We give a structural description of the class C of graphs that do not contain a cycle with a unique chord as an induced subgraph. Our main theorem states that any connected graph in C is a either in some simple basic class or has a decomposition. Basic classes are cliques, bipartite graphs with one side containing only nodes of degree two and induced subgraph of the famous Heawood or Petersen graph. Decompositions are node cutsets consisting of one or two nodes and edge cutsets called 1-joins. Our decomposition theorem actually gives a complete structure theorem for C, i.e. every graph in C can be built from basic graphs that can be explicitly constructed, and gluing them together by prescribed composition operations ; and all graphs built this way are in C. This has several consequences : an O(nm)-time algorithm to decide whether a graph is in C, an O(n+m)-time algorithm that finds a maximum clique of any graph in C and an O(nm)-time coloring algorithm for graphs in C. We prove that every graph in C is either 3-colorable or has a coloring with ω colors where ω is the size of a largest clique. The problem of finding a maximum stable set for a graph in C is known to be NP-hard., Soit C la classe de graphes ne contenant pas de cycle avec une seule corde en tant que sous-graphe induit. Nous montrons que tout graphe de C est ou bien "basique" ou bien "décomposable". Par graphe basique, nous entendons : clique, graphe biparti avec un côté ne contenant que des sommets de degré 2, et sous-graphe induit du graphe de Petersen ou de Heawood. Par décomposable, nous entendons : possédant un sommet ou une paire de sommets d'articulation ou possédant un 1-joint. Notre résultat est un théorème de structure, c'est-à-dire qu'il est réversible. Nous prouvons quelques conséquences : la preuve que tout graphe de C est ou bien coloriable avec 3 couleurs, ou bien avec ω couleurs où ω est la taille d'une plus grande clique. Nous donnons un algorithme de coloration en O(nm). Nous donnons un algorithme de reconnaissance en O(nm) pour la classe C. Cet algorithme répond à des questions intéressantes concernant la détection de sous-graphes induits.

Extended abstract; International audience

We present a polynomial algorithm for recognizing whether a graph is perfect, thus settling a long standing open question. The algorithm uses a decomposition theorem of Conforti, Cornuejols and Vuskovic. Another polynomial algorithm for recognizing perfect graphs, which does not use decomposition, was obtained simultaneously by Chudnovsky and Seymour. Both algorithms need a first phase developed jointly by Chudnovsky, Cornuejols, Liu, Seymour and Vuskovic.

Bruce Reed asks the following question: Can we determine whether a bipartite graph contains a chordless cycle whose length is a multiple of 4? We show that the two following more general questions are equivalent and we provide an answer. Given a bipartite graph G where each edge is assigned a weight +1 or −1, • • determine whether G contains a cycle whose weight is a multiple of 4, • • determine whether G contains a chordless cycle whose weight is a multiple of 4. Given a bipartite graph, we can also decide whether it is possible to assign weights +1 or −1 to its edges so that the above two properties hold.

A hole in a graph is a chordless cycle of length greater than three. In this paper we present a decomposition theorem for graphs that contain no even hole. This theorem yields a polytime algorithm to recognize whether a graph contains an even hole.

In a graph, a chordless cycle of length greater than three is called a hole. Let γ be a {0, 1} vector whose entries are in one-to-one correspondence with the holes of a graphG. We characterize graphs for which, for all choices of the vector γ, we can pick a subsetF of the edge set ofG such that |F ∪H| эγH (mod 2), for all holesH ofG and |F ∪T| э 1 for all trianglesT ofG. We call these graphsuniversally signable. The subsetF of edges is said to be labelledodd. All other edges are said to be labelledeven. Clearly graphs with no holes (triangulated graphs) are universally signable with a labelling of odd on all edges, for all choices of the vector γ. We give a decomposition theorem which leads to a good characterization of graphs that are universally signable. This is a generalization of a theorem due to Hajnal and Suranyi [3] for triangulated graphs.

A graph is signable to be without odd holes if we can assign labels “even” or “odd” to its edges in such a way that the number of edges labelled “odd” in every triangle is odd and the number of edges labelled “odd” in every chordless cycle of length greater than three is even. Note that a graph has no odd holes if it is signed to be without odd holes with every edge having an “odd” label. We derive a co-NP characterization of such graphs.

We prove a theorem about cutsets in partitionable graphs that generalizes earlier results on amalgams, 2-amalgams and homogeneous pairs.

A graph is Berge if no induced subgraph of G is an odd cycle of length at least five or the complement of one. In this paper we give an algorithm to test if a graph G is Berge, with running time O(|V (G)|9). This is independent of the recent proof of the strong perfect graph conjecture.

In this paper we consider the class of simple graphs defined by excluding, as induced subgraphs, even holes (i.e., chordless cycles of even length) and diamonds (i.e., a graph obtained from a clique of size 4 by removing an edge). We say that such graphs are (even-hole, diamond)-free. For this class of graphs we first obtain a decomposition theorem, using clique cutsets, bisimplicial cutsets (which is a special type of a star cutset) and 2-joins. This decomposition theorem is then used to prove that every graph that is (even-hole, diamond)-free contains a simplicial extreme (i.e., a vertex that is either of degree 2 or whose neighborhood induces a clique). This characterization implies that for every (even-hole, diamond)-free graph G, @g(G)=

Consider the following total order: order the vertices by repeatedly removing a vertex of minimum degree in the subgraph of vertices not yet chosen and placing it after all the remaining vertices but before all the vertices already removed. For which graphs the greedy algorithm on this order gives an optimum vertex-coloring? Markossian, Gasparian and Reed introduced the class of β -perfect graphs. These graphs admit such a greedy vertex-coloring algorithm. The recognition of β -perfect graphs is open. We define a subclass of β -perfect graphs, that can be recognized in polynomial time, by considering the class of graphs with no even hole, no short-chorded cycle on six vertices, and no diamond. In particular, we make use of the following properties: no minimal β -imperfect graph contains a simplicial vertex, a minimal β -imperfect graph which is not an even hole contains no vertex of degree 2.

A 0,±1 matrix is balanced if, in every submatrix with two nonzero entries per row and column, the sum of the entries is a multiple of 4. This definition was introduced by Truemper and generalizes the notion of balanced 0,1 matrix introduced by Berge. In this tutorial, we survey what is currently known about these matrices: polyhedral results, combinatorial and structural theorems, and recognition algorithms.

We prove that square-free perfect graphs are bipartite graphs or line graphs of bipartite graphs or have a 2-join or a star cutset.

An even-hole-free graph is a graph that does not contain, as an induced subgraph, a chordless cycle of even length. A graph is triangulated if it does not contain any chordless cycle of length greater than three, as an induced subgraph. We prove that every even-hole-free graph has a node whose neighborhood is triangulated. This implies that in an even-hole-free graph, with n nodes and m edges, there are at most n+2m maximal cliques. It also yields an O(n2m) algorithm that generates all maximal cliques of an even-hole-free graph. In fact these results are obtained for a larger class of graphs that contains even-hole-free graphs.

A graph is a 1-join composition if its vertex set can be partitioned into four nonempty sets A L , A R , S L and S R such that: every vertex of A L is adjacent to every vertex of A R ; no vertex of S L is adjacent to a vertex of A R U S R ; no vertex of S R is adjacent to a vertex of A L U S L ; The graph sandwich problem for 1-join composition is denned as follows: Given a vertex set V , a forced edge set E 1 , and a forbidden edge set E 13 , is there a graph G = (V, E ) such that E l ⊆ E and E ∩ E 3 = φ , which is a 1-join composition graph? We prove that the graph sandwich problem for 1-join composition is NP -complete. This result stands in contrast to the case where S L = φ ( S R = φ ), namely, the graph sandwich problem for homogeneous set, which has a polynomial-time solution.