Artículo
Bonomo, F.; Durán, G.; Safe, M.D.; Wagler, A.K. "Balancedness of subclasses of circular-arc graphs" (2014) Discrete Mathematics and Theoretical Computer Science. 16(3):1-22
Estamos trabajando para incorporar este artículo al repositorio
Consulte la política de Acceso Abierto del editor
Abstract:
A graph is balanced if its clique-vertex incidence matrix contains no square submatrix of odd order with exactly two ones per row and per column. There is a characterization of balanced graphs by forbidden induced subgraphs, but no characterization by mininal forbidden induced subgraphs is known, not even for the case of circular-arc graphs. A circular-arc graph is the intersection graph of a family of arcs on a circle. In this work, we characterize when a given graph G is balanced in terms of minimal forbidden induced subgraphs, by restricting the analysis to the case where G belongs to certain classes of circular-arc graphs, including Helly circular-arc graphs, claw-free circular-arc graphs, and gem-free circular-arc graphs. In the case of gem-free circular-arc graphs, analogous characterizations are derived for two superclasses of balanced graphs: clique-perfect graphs and coordinated graphs. © 2014 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France.
Registro:
| Documento: | Artículo |
| Título: | Balancedness of subclasses of circular-arc graphs |
| Autor: | Bonomo, F.; Durán, G.; Safe, M.D.; Wagler, A.K. |
| Filiación: | CONICET and Depto. de Computación, FCEyN, Universidad de Buenos Aires, Argentina CONICET and Depto. de Matemática and Instituto de Cálculo, FCEyN, Universidad de Buenos Aires, Argentina Depto. de Ingeniería Industrial, FCFM, Universidad de Chile, Santiago, Chile Instituto de Ciencias, Universidad Nacional de General Sarmiento, Los Polvorines, Argentina CNRS and LIMOS, UFR Sciences et Technologies, Université Blaise Pascal, Clermont-Ferrand, France |
| Palabras clave: | Balanced graphs; Circular-arc graphs; Clique-perfect graphs; Coordinated graphs; Perfect graphs; Characterization; Graphic methods; Balanced graphs; Circular-arc graph; Clique-perfect graphs; Coordinated graphs; Perfect graph; Graph theory |
| Año: | 2014 |
| Volumen: | 16 |
| Número: | 3 |
| Página de inicio: | 1 |
| Página de fin: | 22 |
| Título revista: | Discrete Mathematics and Theoretical Computer Science |
| Título revista abreviado: | Discrete Math. Theor. Comput. Sci. |
| ISSN: | 14627264 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v16_n3_p1_Bonomo |
Referencias:
- Berge, C., (1961) Färbung von Graphen, Deren Sämtliche Beziehungsweise, Deren Ungerade Kreise Starr Sind (Zusammenfassung), 10, pp. 114-115. , Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturwiss. Reihe
- Berge, C., Balanced matrices (1972) Math. Program., 2 (1), pp. 19-31
- Berge, C., Chvátal, V., Introduction (1984) Topics on Perfect Graphs Volume 88 of North-Holland Mathematics Studies, pp. vii-xiv. , Noth-Holland
- Berge, C., Las Vergnas, M., Sur un th'eor'eme du type König pour hypergraphes (1970) Ann. N.Y. Acad. Sci., 175, pp. 32-40
- Bonomo, F., Chudnovsky, M., Duran, G., Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs (2008) Discrete Applied Mathematics, 156 (7), pp. 1058-1082. , DOI 10.1016/j.dam.2007.05.048, PII S0166218X07002879
- Bonomo, F., Chudnovsky, M., Durán, G., Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs (2009) Discrete Math., 309 (11), pp. 3485-3499
- Bonomo, F., Durán, G., Grippo, L.N., Safe, M.D., Partial characterizations of circular-arc graphs (2009) J. Graph Theory, 61 (4), pp. 289-306
- Bonomo, F., Durán, G., Groshaus, M., Coordinated graphs and clique graphs of clique-Helly perfect graphs (2007) Util. Math., 72, pp. 175-191
- Bonomo, F., Duran, G., Lin, M.C., Szwarcfiter, J.L., On balanced graphs (2006) Mathematical Programming, 105 (2-3), pp. 233-250. , DOI 10.1007/s10107-005-0651-y
- 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
- Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K., Balancedness of some subclasses of circulararc graphs (2010) Electron. Notes Discrete Math., 36, pp. 1121-1128
- Bonomo, F., Durán, G., Soulignac, F., Sueiro, G., Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs (2009) Discrete Appl. Math., 157 (17), pp. 3511-3518
- Bonomo, F., Durán, G., Soulignac, F., Sueiro, G., Partial characterizations of coordinated graphs: Line graphs and complements of forests (2009) Math. Methods Oper. Res., 69 (2), pp. 251-270
- Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R., The strong perfect graph theorem (2006) Annals of Mathematics, 164 (1), pp. 51-229. , http://projecteuclid.org/Dienst/Repository/1.0/Disseminate/euclid.annm/ 1157656789/body/pdf
- Chvátal, V., On certain polytopes associated with graphs (1975) J. Combin. Theory Ser. B, 18 (2), pp. 138-154
- Durán, G., Lin, M.C., Szwarcfiter, J.L., On clique-transversal and clique-independent sets (2002) Ann. Oper. Res., 116 (1), pp. 71-77
- Fulkerson, D.R., Gross, O.A., Incidence matrices and interval graphs (1965) Pacific J. Math., 15 (3), pp. 835-855
- Fulkerson, D.R., Hoffman, A.J., Oppenheim, R., On balanced matrices (1974) Pivoting and Extensions: In Honor of A.W. Tucker, Volume 1 of Mathematical Programming Study, pp. 120-133. , M. Balinski, editor, North-Holland, Amsterdam
- Gavril, F., Algorithms on circular-arc graphs (1974) Networks, 4, pp. 357-369
- Guruswami, V., Pandu Rangan, C., Algorithmic aspects of clique-transversal and cliqueindependent sets (2000) Discrete Appl. Math., 100 (3), pp. 183-202
- Helly, E., Über Mengen konvexer Körper mit gemeinschaftlichen Punkten (1923) Jber. Deutsch. Math.- Vereining., 32, pp. 175-176
- Hoffman, A.J., Kruskal, J.B., Integral boundary points of convex polyhedra (1956) Linear Inequalities and Related Systems, Volume 38 of Annals of Mathematics Studies, pp. 247-254. , H. W. Kuhn and A.W. Tucker, editors, Princeton University Press
- Joeris, B.L., Lin, M.C., McConnell, R.M., Spinrad, J.P., Szwarcfiter, J.L., Linear-time recognition of Helly circular-arc models and graphs (2011) Algorithmica, 59 (2), pp. 215-239
- Klee, V., What are the intersection graphs of arcs in a circle? (1969) Am. Math. Mon., 76, pp. 810-813
- Lakshmanan, S.A., Vijayakumar, A., The hti-property of some classes of graphs (2009) Discrete Math., 309 (1), pp. 259-263
- Lovász, L., Normal hypergraphs and the perfect graph conjecture (1972) Discrete Math., 2 (3), pp. 253-267
- McConnell, R.M., Linear-time recognition of circular-arc graphs (2003) Algorithmica, 37 (2), pp. 93-147
- Prisner, E., Hereditary clique-Helly graphs (1993) J. Combin. Math. Combin. Comput., 14, pp. 216-220
- Trotter, W.T., Moore, J.I., Characterization problems for graphs, partially ordered sets, lattices, and families of sets (1976) Discrete Math., 16 (4), pp. 361-381
- Tucker, A., Matrix characterizations of circular-arc graphs (1971) Pacific J. Math., 38, pp. 535-545
- Tucker, A., Structure theorems for some circular-arc graphs (1974) Discrete Math., 7, pp. 167-195
- Tucker, A., Coloring a family of circular arcs (1975) SIAM J. Appl. Math., 29 (3), pp. 493-502
- Tucker, A., An efficient test for circular-arc graphs (1980) SIAM J. Comput., 9, pp. 1-24
Citas:
---------- APA ----------
Bonomo, F., Durán, G., Safe, M.D. & Wagler, A.K. (2014) . Balancedness of subclasses of circular-arc graphs. Discrete Mathematics and Theoretical Computer Science, 16(3), 1-22.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v16_n3_p1_Bonomo [ ]
---------- CHICAGO ----------
Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K. "Balancedness of subclasses of circular-arc graphs" . Discrete Mathematics and Theoretical Computer Science 16, no. 3 (2014) : 1-22.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v16_n3_p1_Bonomo [ ]
---------- MLA ----------
Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K. "Balancedness of subclasses of circular-arc graphs" . Discrete Mathematics and Theoretical Computer Science, vol. 16, no. 3, 2014, pp. 1-22.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v16_n3_p1_Bonomo [ ]
---------- VANCOUVER ----------
Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K. Balancedness of subclasses of circular-arc graphs. Discrete Math. Theor. Comput. Sci. 2014;16(3):1-22.Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v16_n3_p1_Bonomo [ ]
