Given a class G of graphs, probe G graphs are defined as follows. A graph G is probe G if there exists a partition of its vertices into a set of probe vertices and a stable set of nonprobe vertices in such a way that non-edges of G, whose endpoints are nonprobe vertices, can be added so that the resulting graph belongs to G. We investigate probe 2-clique graphs and probe diamond-free graphs. For probe 2-clique graphs, we present a polynomial-time recognition algorithm. Probe diamond-free graphs are characterized by minimal forbidden induced subgraphs. As a by-product, it is proved that the class of probe block graphs is the intersection between the classes of chordal graphs and probe diamond-free graphs.
en_US
Patrocinador
dc.description.sponsorship
ANPCyT
PICT 2012-1324
UBACyT
20020130100808BA
CONICET (Argentina)
PIP 112-201201-00450CO
Brazilian research agency FAPERJ
Brazilian research agency CNPq
FONDECyT
1140787
Millennium Science Institute "Complex Engineering Systems" (Chile)
Brazilian research agency CAPES
Lenguage
dc.language.iso
en_US
en_US
Publisher
dc.publisher
Discrete Mathematics and Theoretical Computer Science
A new class of graphs related to perfect graphs is defined in this work: coordinated graphs. A graph G is coordinated if the cardinality of a maximum set of cliques of H with a common vertex is equal to the cardinality of ...
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 ...
Circular-arc graphs are the intersection graphs of open arcs on a circle. Circle graphs are
the intersection graphs of chords on a circle. These graph classes have been the subject
of much study for many years and numerous ...