Search

A graph is balanced when its clique matrix is balanced. Bonomo, Durán, Lin and Szwarcfiter (2006) proved that a graph is balanced if and only if it contains no induced subgraphs known as extended odd suns. However, a characterization of balanced graphs by minimal forbidden induced subgraphs is not known. In this work, we find such a characterization when restricted to the class of claw-free graphs. As a consequence, we prove that there is an O(m2 + n)-time algorithm that, given any graph, either decides that it is balanced or gives a certificate of the fact that it is not claw-free balanced. [ABSTRACT FROM AUTHOR]

A Helly circular-arc graph is the intersection graph of a set of arcs on a circle having the Helly property. We introduce essential obstacles, which are a refinement of the notion of obstacles, and prove that essential obstacles are precisely the minimal forbidden induced circular-arc subgraphs for the class of Helly circular-arc graphs. We show that it is possible to find in linear time, in any given obstacle, some minimal forbidden induced subgraph for the class of Helly circular-arc graphs contained as an induced subgraph. Moreover, relying on an existing linear-time algorithm for finding induced obstacles in circular-arc graphs, we conclude that it is possible to find in linear time an induced essential obstacle in any circular-arc graph that is not a Helly circular-arc graph. The problem of finding a forbidden induced subgraph characterization, not restricted only to circular-arc graphs, for the class of Helly circular-arc graphs remains unresolved. As a partial answer to this problem, we find the minimal forbidden induced subgraph characterization for the class of Helly circular-arc graphs restricted to graphs containing no induced claw and no induced 5-wheel. Furthermore, we show that there is a linear-time algorithm for finding, in any given graph that is not a Helly circular-arc graph, an induced subgraph isomorphic to claw, 5-wheel, or some minimal forbidden induced subgraph for the class of Helly circular-arc graphs. [ABSTRACT FROM AUTHOR]

A family of sets is (p , q) - intersecting if every nonempty subfamily of p or fewer sets has at least q elements in its total intersection. A family of sets has the (p , q) - Helly property if every nonempty (p , q) -intersecting subfamily has total intersection of cardinality at least q. The (2 , 1) -Helly property is the usual Helly property. A hypergraph is (p , q) - Helly if its edge family has the (p , q) -Helly property and hereditary (p , q) -Helly if each of its subhypergraphs has the (p , q) -Helly property. A graph is (p , q) - clique-Helly if the family of its maximal cliques has the (p , q) -Helly property and hereditary (p , q) -clique-Helly if each of its induced subgraphs is (p , q) -clique-Helly. The classes of (p , q) - biclique-Helly and hereditary (p , q) -biclique-Helly graphs are defined analogously. In this work, we prove several characterizations of hereditary (p , q) -Helly hypergraphs, including one by minimal forbidden partial subhypergraphs. On the algorithmic side, we give an improved time bound for the recognition of (p , q) -Helly hypergraphs for each fixed q and show that the recognition of hereditary (p , q) -Helly hypergraphs can be solved in polynomial time if p and q are fixed and co-NP-complete if p is part of the input. In addition, we generalize the characterization of p -clique-Helly graphs in terms of expansions to (p , q) -clique-Helly graphs and give different characterizations of hereditary (p , q) -clique-Helly graphs, including one by forbidden induced subgraphs. We give an improvement on the time bound for the recognition of (p , q) -clique-Helly graphs and prove that the recognition problem of hereditary (p , q) -clique-Helly graphs is polynomial-time solvable for p and q fixed and NP-hard if p or q is part of the input. Finally, we provide different characterizations, give recognition algorithms, and prove hardness results for (p , q) -biclique-Helly graphs and hereditary (p , q) -biclique-Helly graphs which are analogous to those for (p , q) -clique-Helly and hereditary (p , q) -clique-Helly 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]

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]

A normal Helly circular-arc graph is the intersection graph of a set of arcs on a circle of which no three or less arcs cover the whole circle. Lin et al. (2013) characterized circular-arc graphs that are not normal Helly circular-arc graphs, and used them to develop the first recognition algorithm for this graph class. As open problems, they ask for the forbidden subgraph characterization and a direct recognition algorithm for normal Helly circular-arc graphs, both of which are resolved by the current paper. Moreover, when the input is not a normal Helly circular-arc graph, our recognition algorithm finds in linear time a minimal forbidden induced subgraph as a certificate. Our approach yields also a considerably simpler algorithm for the certifying recognition of proper Helly circular-arc graphs, a subclass of normal Helly circular-arc graphs. [ABSTRACT FROM AUTHOR]

A graph is circle if its vertices are in correspondence with a family of chords in a circle in such a way that every two distinct vertices are adjacent if and only if the corresponding chords have nonempty intersection. Even though there are diverse characterizations of circle graphs, a structural characterization by minimal forbidden induced subgraphs for the entire class of circle graphs is not known, not even restricted to split graphs (which are the graphs whose vertex set can be partitioned into a clique and a stable set). In this work, we give a characterization by minimal forbidden induced subgraphs of circle graphs, restricted to split graphs. [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]

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]

We initiate the study of graph classes of power-bounded clique-width, that is, graph classes for which there exist integers k and ℓ such that the k th powers of the graphs are of clique-width at most ℓ . We give sufficient and necessary conditions for this property. As our main results, we characterize graph classes of power-bounded clique-width within classes defined by either one forbidden induced subgraph, or by two connected forbidden induced subgraphs. We also show that for every positive integer k , there exists a graph class such that the k th powers of graphs in the class form a class of bounded clique-width, while this is not the case for any smaller power. [ABSTRACT FROM AUTHOR]

The matching number of a graph is the maximum size of a set of vertex-disjoint edges. The transversal number is the minimum number of vertices needed to meet every edge. A graph has the König–Egerváry property if its matching number equals its transversal number. Lovász proved a characterization of graphs having the König–Egerváry property by means of forbidden subgraphs within graphs with a perfect matching. Korach, Nguyen, and Peis proposed an extension of Lovász’s result to a characterization of all graphs having the König–Egerváry property in terms of forbidden configurations (which are certain arrangements of a subgraph and a maximum matching). In this work, we prove a characterization of graphs having the König–Egerváry property by means of forbidden subgraphs which is a strengthened version of the characterization by Korach et al. Using our characterization of graphs with the König–Egerváry property, we also prove a forbidden subgraph characterization for the class of edge-perfect graphs. [ABSTRACT FROM AUTHOR]

A graph is probe (unit) interval if its vertices can be partitioned into two sets: a set of probe vertices and a set of nonprobe vertices, so that the set of nonprobe vertices is a stable set and it is possible to obtain a (unit) interval graph by adding edges with both endpoints in the set of nonprobe vertices. Probe (unit) interval graphs form a superclass of (unit) interval graphs. Probe interval graphs were introduced by Zhang for an application concerning the physical mapping of DNA in the human genome project. The main results of this article are minimal forbidden induced subgraphs characterizations of probe interval and probe unit interval graphs within two superclasses of cographs: P4-tidy graphs and tree-cographs. Furthermore, we introduce the concept of graphs class with a companion which allows to describe all the minimally non-(probe 풢) graphs with disconnected complement for every graph class 풢 with a companion. [ABSTRACT FROM AUTHOR]