Search

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]

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]

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]

Abstract: The clique-transversal number τ c(G) of a graph G is the minimum size of a set of vertices meeting all the cliques. The clique-independence number α c(G) of G is the maximum size of a collection of vertex-disjoint cliques. A graph is clique-perfect if these two numbers are equal for every induced subgraph of G. Unlike perfect graphs, the class of clique-perfect graphs is not closed under graph complementation nor is a characterization by forbidden induced subgraphs known. Nevertheless, partial results in this direction have been obtained. For instance, in [Bonomo, F., M. Chudnovsky and G. Durán, Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs, Discrete Appl. Math. 156 (2008), pp. 1058–1082], a characterization of those line graphs that are clique-perfect is given in terms of minimal forbidden induced subgraphs. Our main result is a characterization of those complements of line graphs that are clique-perfect, also by means of minimal forbidden induced subgraphs. This implies an O(n2) time algorithm for deciding the clique-perfectness of complements of line graphs and, for those that are clique-perfect, finding α c and τ c. [Copyright &y& Elsevier]

Abstract: In a previous paper [Torres, L.M. and A.K. Wagler, Encoding the dynamics of deterministic systems, Preprint 09-29, Otto-von-Guericke Universität, FMA (2009)] we proposed a compact model for encoding the dynamic behavior of certain discrete deterministic systems based on extending the widely accepted framework of Petri nets. Here, the problem of reconstructing such a model from experimental data obtained by observation of dynamic processes in the system is addressed. This is equivalent to inferring a valid orientation of a certain transition conflict graph. For a special class of systems where the corresponding valid orientations are acyclic, we present a lower bound on the number of experiments required for model reconstruction and show that it is not possible to devise a solution strategy that achieves this bound for every instance. [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: A main result in combinatorial optimization is that clique and chromatic number of a perfect graph are computable in polynomial time (Grötschel, Lovász and Schrijver 1981). The circular-clique and circular-chromatic number are well-studied refinements of these graph parameters, and circular-perfect graphs form the corresponding superclass of perfect graphs. So far, it is unknown whether the (weighted) circular-clique and circular-chromatic number of a circular-perfect graph are computable in polynomial time. In this paper, we show the polynomial time computability of these two graph parameters for some super-classes of perfect graphs with the help of polyhedral arguments. [Copyright &y& Elsevier]

Abstract: A {0, 1}-matrix is balanced if it contains no square submatrix of odd order with exactly two 1''s per row and per column. Balanced matrices lead to ideal formulations for both set packing and set covering problems. Balanced graphs are those graphs whose clique-vertex incidence matrix is balanced. 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 some graph classes which also lead to polynomial time or even linear time recognition algorithms within the corresponding subclasses. [Copyright &y& Elsevier]

Perfect graphs constitute a well-studied graph class with a rich structure, 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) coincides with the fractional stable set polytope QSTAB(G). For all imperfect graphs G it holds that STAB(G) ⊂ QSTAB(G). It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away from being perfect. We discuss three different concepts, involving the facet set of STAB(G), the disjunctive index of QSTAB(G), and the dilation ratio of the two polytopes. Including only certain types of facets for STAB(G), we obtain graphs that are in some sense close to perfect graphs, for example minimally imperfect graphs, and certain other classes of so-called rank-perfect graphs. The imperfection ratio has been introduced by Gerke and McDiarmid as the dilation ratio of STAB(G) and QSTAB(G), whereas Aguilera et al. suggest to take the disjunctive index of QSTAB(G) as the imperfection index of G. For both invariants there exist no general upper bounds, but there are bounds known for the imperfection ratio of several graph classes. Outgoing from a graph-theoretical interpretation of the imperfection index, we prove that there exists no upper bound on the imperfection index for those graph classes with a known bounded imperfection ratio. Comparing the two invariants on those classes, it seems that the imperfection index measures imperfection much more roughly than the imperfection ratio; we, therefore, discuss possible directions for refinements. [ABSTRACT FROM AUTHOR]

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: Circular-perfect graphs form a natural superclass of the well-known perfect graphs by means of a more general coloring concept. For perfect graphs, a characterization by means of forbidden subgraphs was recently settled by Chudnovsky et al. [Chudnovsky, M., N. Robertson, P. Seymour, and R. Thomas, The Strong Perfect Graph Theorem, Annals of Mathematics 164 (2006) 51–229]. It is, therefore, natural to ask for an analogous characterization for circular-perfect graphs or, equivalently, for a characterization of all minimally circular-imperfect graphs. Our focus is the circular-(im)perfection of triangle-free graphs. We exhibit several different new infinite families of minimally circular-imperfect triangle-free graphs. This shows that a characterization of circular-perfect graphs by means of forbidden subgraphs is a difficult task, even if restricted to the class of triangle-free graphs. This is in contrary to the perfect case where it is long-time known that the only minimally imperfect triangle-free graphs are the odd holes [Tucker, A., Critical Perfect Graphs and Perfect 3-chromatic Graphs, J. Combin. Theory (B) 23 (1977) 143–149]. [Copyright &y& Elsevier]

Abstract: Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations w.r.t different concepts. Perfect graphs are, e.g., characterized as precisely those graphs G where the stable set polytope STAB(G) coincides with the clique constraint stable set polytope QSTAB(G). For all imperfect graphs STAB(G) ⊂ QSTAB(G) holds and, therefore, it is natural to measure imperfection in terms of the difference between STAB(G) and QSTAB(G). Several concepts have been developed in this direction, for instance the dilation ratio of STAB(G) and QSTAB(G) which is equivalent to the imperfection ratio imp(G) of G. T determine imp(G), both knowledge on the facets of STAB(G) and the extreme points of QSTAB(G) is required. For that, we extend a well-known result on antiblocking polyhedra by establishing a 1-1 correspondence between extreme points of QSTAB(G) and facet-defining subgraphs of . We discuss several consequences, in particular, we give alternative proofs of several well-known results. [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]

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]

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]

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]