Browsing by Author "Bonomo, Flavia"

Now showing items 1-11 of 11

    • b-Coloring is NP-hard on Co-bipartite Graphs and Polytime Solvable on Tree-Cographs 
      Bonomo, Flavia; Schaudt, Oliver; Stein, Maya; Valencia Pabón, Mario (Springer, 2015)
      A b-coloring of a graph is a proper coloring such that every color class contains a vertex that is adjacent to all other color classes. The b-chromatic number of a graph , denoted by , is the maximum number such that admits ...
    • Clique-perfectness of complements of line graphs 
      Bonomo, Flavia; Durán, Guillermo; Safe, Martín D.; Wagler, Annegret K. (Elsevier, 2015)
      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 ...
    • Coordinated graphs and clique graphs of clique-Helly perfect graphs 
      Bonomo, Flavia; Durán Maggiolo, Guillermo; Groshaus, Marina (2007)
      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 ...
    • Forbidden subgraphs and the König–Egerváry property 
      Bonomo, Flavia; Dourado, Mitre C.; Durán Maggiolo, Guillermo; Faria, Luerbio; Grippo, Luciano N.; Safe, Martín D. (Elsevier, 2013)
      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 ...
    • Minimum sum set coloring of trees and line graphs of trees 
      Bonomo, Flavia; Durán Maggiolo, Guillermo; Marenco, Javier; Valencia Pabon, Mario (Elsevier, 2011)
      In this paper, we study the minimum sum set coloring (MSSC) problem which consists in assigning a set of x(v) positive integers to each vertex v of a graph so that the intersection of sets assigned to adjacent vertices ...
    • NP-completeness results for edge modification problems 
      Burzyn, Pablo; Bonomo, Flavia; Durán Maggiolo, Guillermo (ELSEVIER, 2006-08-15)
      The aim of edge modification problems is to change the edge set of a given graph as little as possible in order to satisfy a certain property. Edge modification problems in graphs have a lot of applications in different ...
    • On balanced graphs 
      Bonomo, Flavia; Durán Maggiolo, Guillermo; Lin, Min Chih; Szwarcfiter, Jayme L. (SPRINGER, 2006-02)
      Berge defined a hypergraph to be balanced if its incidence matrix is balanced. We consider this concept applied to graphs, and call a graph to be balanced when its clique matrix is balanced. Characterizations of balanced ...
    • On minimal forbidden subgraph characterizations of balanced graphs 
      Bonomo, Flavia; Durán Maggiolo, Guillermo; Safe, Martín D.; Wagler, Annegret K. (2013)
      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 ...
    • On probe 2-clique graphs and probe diamond-free graphs 
      Bonomo, Flavia; Figueiredo, Celina de; Durán Maggiolo, Guillermo; Grippo, Luciano; Safe, Martín; Szwarcfiter, Jayme (Discrete Mathematics and Theoretical Computer Science, 2015)
      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 ...
    • A one-to-one correspondence between potential solutions ofthe cluster deletion problem and the minimum sum ... 
      Bonomo, Flavia; Durán Maggiolo, Guillermo; Napoli, Amedeo; Valencia Pabon, Mario (Elsevier, 2015)
      In this note we show a one-to-one correspondence between potentially optimal solutions to the cluster deletion problem in a graph Gand potentially optimal solutions for the minimum sum coloring problem in G(i.e. the ...
    • Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs 
      Bonomo, Flavia; Chudnovsky, Maria; Durán Maggiolo, Guillermo (ELSEVIER, 2008-04-01)
      A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. The clique-transversal number and clique-independence ...