On minimal forbidden subgraph characterizations of balanced graphs

dc.creatorBonomo, Flavia
dc.creatorDuran, Guillermo Alfredo
dc.creatorSafe, Martin Dario
dc.creatorWagler, Annegret K.
dc.date.accessioned2017-06-23T21:06:43Z
dc.date.accessioned2018-11-06T11:42:11Z
dc.date.available2017-06-23T21:06:43Z
dc.date.available2018-11-06T11:42:11Z
dc.date.created2017-06-23T21:06:43Z
dc.date.issued2013-09
dc.identifierBonomo, Flavia; Duran, Guillermo Alfredo; Safe, Martin Dario; Wagler, Annegret K.; On minimal forbidden subgraph characterizations of balanced graphs; Elsevier Science; Discrete Applied Mathematics; 161; 13-14; 9-2013; 1925-1942
dc.identifier0166-218X
dc.identifierhttp://hdl.handle.net/11336/18827
dc.identifierCONICET Digital
dc.identifierCONICET
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1858045
dc.description.abstractA 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.
dc.languageeng
dc.publisherElsevier Science
dc.relationinfo:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2013.04.001
dc.relationinfo:eu-repo/semantics/altIdentifier/url/http://www.sciencedirect.com/science/article/pii/S0166218X13001741
dc.rightshttps://creativecommons.org/licenses/by-nc-nd/2.5/ar/
dc.rightsinfo:eu-repo/semantics/restrictedAccess
dc.subjectBalanced graphs
dc.subjectBipartite graphs
dc.subjectHereditary clique.Helly graphs
dc.subjectLine graphs
dc.subjectPerfect graphs
dc.titleOn minimal forbidden subgraph characterizations of balanced graphs
dc.typeArtículos de revistas
dc.typeArtículos de revistas
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución