Search

A graph is called split if its vertex set can be partitioned into a stable set and a clique. In this article, we studied two variants of split graphs. A graph G is polar if its vertex set can be partitioned into two sets A and B such that G[A] is a complete multipartite graph and G[B] is a disjoint union of complete graphs. A 2-unipolar graph is a polar graph G such that G[A] is a clique and G[B] is the disjoint union of complete graphs with at most two vertices. We present a minimal forbidden induced subgraph characterization for 2-unipolar graphs. In addition, we show that they can be represented as an intersection of substars of special cacti. Let G be a graph class, the G-width of a graph G is the minimum positive integer k such that there exist k independent sets N1, ... , Nk such that a set F of nonedges of G, whose endpoints belong to some Ni with i = 1, ... , k, can be added so that the resulting graph G′ belongs to G. We say that a graph G is k-probe-G if it has G-width at most k and when G is the class of split graphs it is denominated k-probe-split. We prove that deciding, given a graph G and a positive integer k, whether G is a h-probe-split graph for some h ≤ k is NP-complete. Besides, a characterization by minimal forbidden induced subgraphs for 2-probe-split cographs is presented. [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 G is a probe unit interval graph if its vertex set can be partitioned into a set P of probe vertices and a stable set N of nonprobe vertices, so that a unit interval graph can be obtained by adding a set of edges whose endpoints belong to N. A partitioned graph is a graph having a prescribed partition into P and N. In this article we present structural characterizations for those partitioned interval graphs and unpartitioned interval graphs which are probe unit interval graphs, in terms of certain characteristics of their interval models. These characterizations lead to characterizations of probe unit interval graphs within the class of interval graphs by minimal forbidden induced subgraphs. [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]

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]

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]

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]