Search

This work is devoted to the study of the Lovász–Schrijver PSD-operator L S + applied to the edge relaxation ESTAB (G) of the stable set polytope STAB (G) of a graph G. In order to characterize the graphs G for which STAB (G) is achieved in one iteration of the L S + -operator, called L S + -perfect graphs, an according conjecture has been recently formulated (L S + -Perfect Graph Conjecture). Here we study two graph classes defined by clique cutsets (pseudothreshold graphs and graphs without certain Truemper configurations). We completely describe the facets of the stable set polytope for such graphs, which enables us to show that one class is a subclass of L S + -perfect graphs, and to verify the L S + -Perfect Graph Conjecture for the other class. [ABSTRACT FROM AUTHOR]

Normal graphs are defined in terms of cross-intersecting set families: a graph is normal if it admits a clique cover Q and a stable set cover S s.t. every clique in Q intersects every stable set in S. Normal graphs can be considered as closure of perfect graphs by means of co-normal products and graph entropy. Perfect graphs have been characterized as those graphs without odd holes and odd antiholes as induced subgraphs (Strong Perfect Graph Theorem, Chudnovsky et al.). Körner and de Simone observed that C5, C7, and C¯7 are minimal not normal and conjectured, in analogy to the Strong Perfect Graph Theorem, that every (C5,C7,C¯7)-free graph is normal (Normal Graph Conjecture, Körner and de Simone). Recently, this conjecture has been disproved by Harutyunyan, Pastor and Thomassé. However, in this paper we verify it for two classes of sparse graphs, 1-trees and cacti. In addition, we provide both linear time recognition algorithms and characterizations for the normal graphs within these two classes. [ABSTRACT FROM AUTHOR]

The context of this work is the reconstruction of Petri net models for biological systems from experimental data. Such methods aim at generating all network alternatives fitting the given data. For a successful reconstruction, the data need to satisfy two properties: reproducibility and monotonicity. In this paper, we focus on a necessary preprocessing step for a recent reconstruction approach. We test the data for reproducibility, provide a feasibility test to detect cases where the reconstruction from the given data may fail, and provide a strategy to cope with the infeasible cases. After having performed the preprocessing step, it is guaranteed that the (given or modified) data are appropriate as input for the main reconstruction algorithm. [ABSTRACT FROM AUTHOR]

A main result of combinatorial optimization is that the clique and chromatic numbers of a perfect graph are computable in polynomial time (Grötschel et al., 1981) [7]. This result relies on polyhedral characterizations of perfect graphs involving the stable set polytope of the graph, a linear relaxation defined by clique constraints, and a semi-definite relaxation, the Theta-body of the graph. A natural question is whether the algorithmic results for perfect graphs can be extended to graph classes with similar polyhedral properties. We consider a superclass of perfect graphs, the -perfect graphs, whose stable set polytope is given by constraints associated with generalized cliques. We show that for such graphs the clique number can be computed in polynomial time as well. The result strongly relies upon Fulkerson’s antiblocking theory for polyhedra and Lovász’s Theta function. [ABSTRACT FROM AUTHOR]

A main result of combinatorial optimization is that clique and chromatic number of a perfect graph are computable in polynomial time (Grötschel et al. in Combinatorica 1(2):169–197, 1981 ). Perfect graphs have the key property that clique and chromatic number coincide for all induced subgraphs; we address the question whether the algorithmic results for perfect graphs can be extended to graph classes where the chromatic number of all members is bounded by the clique number plus one. We consider a well-studied superclass of perfect graphs satisfying this property, the circular-perfect graphs, and show that for such graphs both clique and chromatic number are computable in polynomial time as well. In addition, we discuss the polynomial time computability of further graph parameters for certain subclasses of circular-perfect graphs. All the results strongly rely upon Lovász’s Theta function. [ABSTRACT FROM AUTHOR]

The context of this work is the reconstruction of Petri net models for biological systems from experimental data. Such methods aim at generating all network alternatives fitting the given data. To keep the solution set small while guaranteeing its completeness, the idea is to generate only Petri nets being 'minimal' in the sense that all other networks fitting the data contain the reconstructed ones. In this paper, we consider Petri nets with extensions in two directions: priority relations among the transitions of a network in order to allow modeling deterministic systems, and control-arcs in order to represent catalytic or inhibitory dependencies. We define a containment relation for Petri nets taking both concepts, priority relations and control-arcs, into account. We discuss the consequences for this kind of Petri nets differing in their sets of control-arcs and priority relations, and the impact of our results towards the reconstruction of such Petri nets. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to present a strictly mathematical model for interaction networks, to address the question of steady-state analysis, and to outline an approach for reconstructing models from experimental data. Our expositions require notations and basic results from discrete mathematics. Therefore, we also introduce some elementary background material from this field. [ABSTRACT FROM AUTHOR]

Abstract: Obtaining a complete description of the stable set polytopes of claw-free graphs is a long-standing open problem. Eisenbrand et al. recently achieved a breakthrough for the subclass of quasi-line graphs. As a consequence, every non-trivial facet of their stable set polytope has at most two different, but arbitrarily high left hand side coefficients. For the graphs with stability number 2, Cook showed that all their non-trivial facets are 1/2-valued. For claw-free but not quasi-line graphs with stability number at least 4, Stauffer conjectured that the same holds true. In contrast, there are known claw-free graphs with stability number 3 which induce facets with up to eight different left hand side coefficients. We prove that the situation is even worse: for every positive integer , we exhibit a claw-free graph with stability number 3 inducing a facet with different left hand side coefficients. [Copyright &y& Elsevier]

Abstract: Circular-perfect graphs form a natural superclass of perfect graphs: on the one hand due to their definition by means of a more general coloring concept, on the other hand as an important class of -bound graphs with the smallest non-trivial -binding function . The Strong Perfect Graph Conjecture, recently settled by Chudnovsky et al. [The strong perfect graph theorem, Ann. of Math. 164 (2006) 51–229], provides a characterization of perfect graphs by means of forbidden subgraphs. It is, therefore, natural to ask for an analogous conjecture for circular-perfect graphs, that is for a characterization of all minimal circular-imperfect graphs. At present, not many minimal circular-imperfect graphs are known. This paper studies the circular-(im)perfection of some families of graphs: normalized circular cliques, partitionable graphs, planar graphs, and complete joins. We thereby exhibit classes of minimal circular-imperfect graphs, namely, certain partitionable webs, a subclass of planar graphs, and odd wheels and odd antiwheels. As those classes appear to be very different from a structural point of view, we infer that formulating an appropriate conjecture for circular-perfect graphs, as analogue to the Strong Perfect Graph Theorem, seems to be difficult. [Copyright &y& Elsevier]

Abstract: Graphs with circular symmetry, called webs, are relevant w.r.t. describing the stable set polytopes of two larger graph classes, quasi-line graphs [G. Giles, L.E. Trotter Jr., On stable set polyhedra for -free graphs, J. Combin. Theory B 31 (1981) 313–326; G. Oriolo, Clique family inequalities for the stable set polytope for quasi-line graphs, in: Stability Problems, Discrete Appl. Math. 132 (2003) 185–201 (special issue)] and claw-free graphs [A. Galluccio, A. Sassano, The rank facets of the stable set polytope for claw-free graphs, J. Combin. Theory B 69 (1997) 1–38; G. Giles, L.E. Trotter Jr., On stable set polyhedra for -free graphs, J. Combin. Theory B 31 (1981) 313–326]. Providing a decent linear description of the stable set polytopes of claw-free graphs is a long-standing problem [M. Grötschel, L. Lovász, A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, 1988]. However, even the problem of finding all facets of stable set polytopes of webs is open. So far, it is only known that stable set polytopes of webs with clique number have rank facets only [G. Dahl, Stable set polytopes for a class of circulant graphs, SIAM J. Optim. 9 (1999) 493–503; L.E. Trotter, Jr., A class of facet producing graphs for vertex packing polyhedra, Discrete Math. 12 (1975) 373–388] while there are examples with clique number having non-rank facets [J. Kind, Mobilitätsmodelle für zellulare Mobilfunknetze: Produktformen und Blockierung, Ph.D. Thesis, RWTH Aachen, 2000; T.M. Liebling, G. Oriolo, B. Spille, G. Stauffer, On non-rank facets of the stable set polytope of claw-free graphs and circulant graphs, Math. Methods Oper. Res. 59 (2004) 25; G. Oriolo, Clique family inequalities for the stable set polytope for quasi-line graphs, in: Stability Problems, Discrete Appl. Math. 132 (2003) 185–201 (special issue); A. Pêcher, A. Wagler, On non-rank facets of stable set polytopes of webs with clique number four, Discrete Appl. Math. 154 (2006) 1408–1415]. In this paper, we provide a construction for non-rank facets of stable set polytopes of webs. This construction is the main tool to obtain in a companion paper [A. Pêcher, A. Wagler, Almost all webs are not rank-perfect, Math. Program 105 (2006) 311–328], for all fixed values of that there are only finitely many webs with clique number whose stable set polytopes admit rank facets only. [Copyright &y& Elsevier]

Abstract: Graphs with circular symmetry, called webs, are relevant for describing the stable set polytopes of two larger graph classes, quasi-line graphs and claw-free graphs. Providing a decent linear description of the stable set polytopes of claw-free graphs is a long-standing problem. However, even the problem of finding all facets of stable set polytopes of webs is open. So far, it is only known that stable set polytopes of webs with clique number have rank facets only while there are examples with clique number having non-rank facets. The aim of the present paper is to treat the remaining case with clique number : we provide an infinite sequence of such webs whose stable set polytopes admit non-rank facets. [Copyright &y& Elsevier]

Graphs with circular symmetry, called webs, are crucial for describing the stable set polytopes of two larger graph classes, quasi-line graphs[8,12] and claw-free graphs [7,8]. Providing a complete linear description of the stable set polytopes of claw-free graphs is a long-standing problem [9]. Ben Rebea conjectured a description for quasi-line graphs, see [12]; Chudnovsky and Seymour [2] verified this conjecture recently for quasi-line graphs not belonging to the subclass of fuzzy circular interval graphs and showed that rank facets are required in this case only. Fuzzy circular interval graphs contain all webs and even the problem of finding all facets of their stable set polytopes is open. So far, it is only known that stable set polytopes of webs with clique number ≤3 have rank facets only [5,17] while there are examples with clique number ≥4 having non-rank facets [10_12,15]. In this paper we prove, building on a construction for non-rank facets from [16], that the stable set polytopes of almost all webs with clique number ≥5 admit non-rank facets. This adds support to the belief that these graphs are indeed the core of Ben Rebea's conjecture. Finally, we present a conjecture how to construct all facets of the stable set polytopes of webs. [ABSTRACT FROM AUTHOR]

Circular-perfect graphs form a natural superclass of perfect graphs, introduced by Zhu almost 20 years ago: on the one hand due to their definition by means of a more general coloring concept, on the other hand as an important class of χ -bound graphs with the smallest non-trivial χ -binding function χ (G) ≤ ω (G) + 1. In this paper, we survey the results about circular-perfect graphs obtained in the two last decades, with a focus on whether the fascinating properties of perfect graphs can be extended to this superclass. We recall the deep algorithmic properties of perfect graphs and the underlying polyhedral graph theory, in order to outline in this setting the main graph parameters that are also related to circular-perfect graphs. Finally, we give a list of open problems. [ABSTRACT FROM AUTHOR]

The subject of this work is the study of LS + -perfect graphs defined as those graphs G for which the stable set polytope STAB (G) is achieved in one iteration of Lovász–Schrijver PSD-operator LS + , applied to its edge relaxation ESTAB (G). The recently formulated LS + -Perfect Graph Conjecture aims at a characterization of this family of graphs, through the structure of the facet defining inequalities of the stable set polytope. The main contribution of this work is to verify it for the well-studied class of claw-free graphs. [ABSTRACT FROM AUTHOR]

Abstract: Zhu [X. Zhu, Circular-perfect graphs, J. Graph Theory 48 (2005) 186–209] introduced circular-perfect graphs as a superclass of the well-known perfect graphs and as an important -bound class of graphs with the smallest non-trivial -binding function . Perfect graphs have been recently characterized as those graphs without odd holes and odd antiholes as induced subgraphs [M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, Ann. Math. (in press)]; in particular, perfect graphs are closed under complementation [L. Lovász, Normal hypergraphs and the weak perfect graph conjecture, Discrete Math. 2 (1972) 253–267]. To the contrary, circular-perfect graphs are not closed under complementation and the list of forbidden subgraphs is unknown. We study strongly circular-perfect graphs: a circular-perfect graph is strongly circular-perfect if its complement is circular-perfect as well. This subclass entails perfect graphs, odd holes, and odd antiholes. As the main result, we fully characterize the triangle-free strongly circular-perfect graphs, and prove that, for this graph class, both the stable set problem and the recognition problem can be solved in polynomial time. Moreover, we address the characterization of strongly circular-perfect graphs by means of forbidden subgraphs. Results from [A. Pêcher, A. Wagler, On classes of minimal circular-imperfect graphs, Discrete Math. (in press)] suggest that formulating a corresponding conjecture for circular-perfect graphs is difficult; it is even unknown which triangle-free graphs are minimal circular-imperfect. We present the complete list of all triangle-free minimal not strongly circular-perfect graphs. [Copyright &y& Elsevier]

Perfect graphs constitute a well-studied graph class with a rich structure, which is reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs G where the stable set polytope STAB( G) equals the fractional stable set polytope QSTAB( G). The dilation ratio $${\rm min}\{t : {\rm QSTAB}(G) \subseteq t\,{\rm STAB}(G)\}$$ of the two polytopes yields the imperfection ratio of G. It is NP-hard to compute and, for most graph classes, it is even unknown whether it is bounded. For graphs G such that all facets of STAB( G) are rank constraints associated with antiwebs, we characterize the imperfection ratio and bound it by 3/2. Outgoing from this result, we characterize and bound the imperfection ratio for several graph classes, including near-bipartite graphs and their complements, namely quasi-line graphs, by means of induced antiwebs and webs, respectively. [ABSTRACT FROM AUTHOR]

Perfect graphs form a well-known class of graphs introduced by Berge in the 1960s in terms of a min–max type equality involving two famous graph parameters. In this work, we survey certain variants and subclasses of perfect graphs defined by means of min–max relations of other graph parameters; namely: clique-perfect, coordinated, and neighborhood-perfect graphs. We show the connection between graph classes and both hypergraph theory, the clique graph operator, and some other graph classes. We review different partial characterizations of them by forbidden induced subgraphs, present the previous results, and the main open problems. Computational complexity problems are also discussed. [ABSTRACT FROM AUTHOR]

The problems of determining minimum identifying, locating-dominating or open locating-dominating codes are special search problems that are challenging both from a theoretical and a computational point of view, even for several graph classes where other in general hard problems are easy to solve, like bipartite graphs or chordal graphs. Hence, a typical line of attack for these problems is to determine minimum codes of special graphs. In this work we study the problem of determining the cardinality of minimum such codes in block graphs (that are diamond-free chordal graphs). We present linear-time algorithms for these problems, as a generalization of a linear-time algorithm proposed by Auger in 2010 for identifying codes in trees. Thereby, we provide a subclass of chordal graphs for which all three problems can be solved in linear time. [ABSTRACT FROM AUTHOR]

A graph is clique-perfect if the maximum number of pairwise disjoint maximal cliques equals the minimum number of vertices intersecting all maximal cliques for each induced subgraph. In this work, we give necessary and sufficient conditions for the complement of a line graph to be clique-perfect and an O ( n 2 ) -time algorithm to recognize such graphs. These results follow from a characterization and a linear-time recognition algorithm for matching-perfect graphs, which we introduce as graphs where the maximum number of pairwise edge-disjoint maximal matchings equals the minimum number of edges intersecting all maximal matchings for each subgraph. Thereby, we completely describe the linear and circular structure of the graphs containing no bipartite claw, from which we derive a structure theorem for all those graphs containing no bipartite claw that are Class 2 with respect to edge-coloring. [ABSTRACT FROM AUTHOR]

A graph is balanced if its clique-vertex incidence matrix contains no square submatrix of odd order with exactly two ones per row and per column. There is a characterization of balanced graphs by forbidden induced subgraphs, but no characterization by mininal forbidden induced subgraphs is known, not even for the case of circular-arc graphs. A circular-arc graph is the intersection graph of a family of arcs on a circle. In this work, we characterize when a given graph G is balanced in terms of minimal forbidden induced subgraphs, by restricting the analysis to the case where G belongs to certain classes of circular-arc graphs, including Helly circular-arc graphs, claw-free circular-arc graphs, and gem-free circular-arc graphs. In the case of gem-free circular-arc graphs, analogous characterizations are derived for two superclasses of balanced graphs: clique-perfect graphs and coordinated graphs. [ABSTRACT FROM AUTHOR]

A graph is clique-perfect if the maximum size of a clique-independent set (a set of pairwise disjoint maximal cliques) and the minimum size of a clique-transversal set (a set of vertices meeting every maximal clique) coincide for each induced subgraph. A graph is balanced if its clique-matrix contains no square submatrix of odd size with exactly two ones per row and column. In this work, we give linear-time recognition algorithms and minimal forbidden induced subgraph characterizations of clique-perfectness and balancedness ofP4-tidy graphs and a linear-time algorithm for computing a maximum clique-independent set and a minimum clique-transversal set for anyP4-tidy graph. We also give a minimal forbidden induced subgraph characterization and a linear-time recognition algorithm for balancedness of paw-free graphs. Finally, we show that clique-perfectness of diamond-free graphs can be decided in polynomial time by showing that a diamond-free graph is clique-perfect if and only if it is balanced. [ABSTRACT FROM PUBLISHER]

Abstract: A graph is balanced if its clique-matrix contains no edge–vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work, we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to graphs that belong to one of the following graph classes: complements of bipartite graphs, line graphs of multigraphs, and complements of line graphs of multigraphs. These characterizations lead to linear-time recognition algorithms for balanced graphs within the same three graph classes. [Copyright &y& Elsevier]