Artículo
Bonomo, F.; Durán, G.; Safe, M.D.; Wagler, A.K. "Balancedness of some subclasses of circular-arc graphs" (2010) Electronic Notes in Discrete Mathematics. 36(C):1121-1128
Consulte la política de Acceso Abierto del editor
Abstract:
A graph is balanced if its clique-vertex incidence matrix is balanced, i.e., it does not contain a square submatrix of odd order with exactly two ones per row and per column. Interval graphs, obtained as intersection graphs of intervals of a line, are well-known examples of balanced graphs. A circular-arc graph is the intersection graph of a family of arcs on a circle. Circular-arc graphs generalize interval graphs, but are not balanced in general. In this work we characterize balanced graphs by minimal forbidden induced subgraphs restricted to graphs that belong to some classes of circular-arc graphs. © 2010 Elsevier B.V.
Registro:
| Documento: | Artículo |
| Título: | Balancedness of some subclasses of circular-arc graphs |
| Autor: | Bonomo, F.; Durán, G.; Safe, M.D.; Wagler, A.K. |
| Filiación: | CONICET and Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina CONICET and Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina Departamento de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Santiago, Chile Instituto de Ciencias, Universidad Nacional de General Sarmiento, Los Polvorines, Argentina Institut für Mathematische Optimierung, Fakultät für Mathematik, Otto-von-Guericke-Universität Magdeburg, Germany |
| Palabras clave: | Balanced graphs; Circular-arc graphs; Forbidden subgraphs; Perfect graphs |
| Año: | 2010 |
| Volumen: | 36 |
| Número: | C |
| Página de inicio: | 1121 |
| Página de fin: | 1128 |
| DOI: | http://dx.doi.org/10.1016/j.endm.2010.05.142 |
| Título revista: | Electronic Notes in Discrete Mathematics |
| Título revista abreviado: | Electron. Notes Discrete Math. |
| ISSN: | 15710653 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v36_nC_p1121_Bonomo |
Referencias:
- Berge, C., Färbung von Graphen, deren sämtliche beziehungsweise, deren ungerade Kreise starr sind (Zusammenfassung) (1961) Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Naturwiss. Reihe, 10, pp. 114-115
- Berge, C., Balanced matrices (1972) Math. Program., 2, pp. 19-31
- Bonomo, F., Durán, G., Grippo, L.N., Safe, M.D., Partial characterizations of circular-arc graphs (2009) J. Graph Theory, 61, pp. 289-306
- Bonomo, F., Durán, G., Lin, M.C., Szwarcfiter, J.L., On balanced graphs (2006) Math. Program., 105, pp. 233-250
- Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K., On minimal forbidden subgraph characterizations of balanced graphs (2009) Electron. Notes Discrete Math., 35, pp. 41-46
- Chudnovsky, M., Robertson, N., Seymour, P.D., Thomas, R., The strong perfect graph theorem (2006) Ann. Math., 164, pp. 51-229
- Chvátal, V., On certain polytopes associated with graphs (1975) J. Combin. Theory Ser. B, 18, pp. 138-154
- Dahlhaus, E., Manuel, P.D., Miller, M., Maximum h-colourable subgraph problem in balanced graphs (1998) Inform. Process. Lett., 65, pp. 301-303
- Farber, M., Characterizations of strongly chordal graphs (1983) Discrete Math., 43, pp. 173-189
- Fulkerson, D.R., Hoffman, A.J., Oppenheim, R., On balanced matrices (1974) Pivoting and Extensions: In honor of A.W. Tucker, Math. Program. Study 1, pp. 120-133. , North-Holland, Amsterdam, M. Balinski (Ed.)
- Joeris, B.L., Lin, M.C., McConnell, R.M., Spinrad, J.P., Szwarcfiter, J.L., (2009), Linear-time recognition of Helly circular-arc models and graphs, Algorithmica, in press; Lehel, J., Tuza, Z., Neighborhood perfect graphs (1986) Discrete Math., 61, pp. 93-101
- Prisner, E., Hereditary clique-Helly graphs (1993) J. Combin. Math. Combin. Comput., 14, pp. 216-220
- Tucker, A., Coloring a family of circular arcs (1975) SIAM J. Appl. Math., 29, pp. 493-502
Citas:
---------- APA ----------
Bonomo, F., Durán, G., Safe, M.D. & Wagler, A.K. (2010) . Balancedness of some subclasses of circular-arc graphs. Electronic Notes in Discrete Mathematics, 36(C), 1121-1128.http://dx.doi.org/10.1016/j.endm.2010.05.142
---------- CHICAGO ----------
Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K. "Balancedness of some subclasses of circular-arc graphs" . Electronic Notes in Discrete Mathematics 36, no. C (2010) : 1121-1128.http://dx.doi.org/10.1016/j.endm.2010.05.142
---------- MLA ----------
Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K. "Balancedness of some subclasses of circular-arc graphs" . Electronic Notes in Discrete Mathematics, vol. 36, no. C, 2010, pp. 1121-1128.http://dx.doi.org/10.1016/j.endm.2010.05.142
---------- VANCOUVER ----------
Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K. Balancedness of some subclasses of circular-arc graphs. Electron. Notes Discrete Math. 2010;36(C):1121-1128.http://dx.doi.org/10.1016/j.endm.2010.05.142
