On minimal forbidden subgraph characterizations of balanced graphs
Author
dc.contributor.author
Bonomo, Flavia
Author
dc.contributor.author
Durán Maggiolo, Guillermo
es_CL
Author
dc.contributor.author
Safe, Martín D.
es_CL
Author
dc.contributor.author
Wagler, Annegret K.
es_CL
Admission date
dc.date.accessioned
2014-03-06T19:40:33Z
Available date
dc.date.available
2014-03-06T19:40:33Z
Publication date
dc.date.issued
2013
Cita de ítem
dc.identifier.citation
Discrete Applied Mathematics 161 (2013) 1925–1942
en_US
Identifier
dc.identifier.issn
doi 10.1016/j.dam.2013.04.001
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/126415
General note
dc.description
Artículo de publicación ISI
en_US
Abstract
dc.description.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.