Navegar

Colección

Datos Estadísticas

Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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. © 2013 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:On minimal forbidden subgraph characterizations of balanced graphs
Autor:Bonomo, F.; Durán, G.; Safe, M.D.; Wagler, A.K.
Filiación:CONICET, Argentina
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Departamento de Matemática and Instituto de Cálculo, 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
CNRS, LIMOS, Université Blaise Pascal, Clermont-Ferrand, France
Palabras clave:Balanced graphs; Bipartite graphs; Hereditary clique-Helly graphs; Line graphs; Perfect graphs; Balanced graphs; Bipartite graphs; Hereditary clique-Helly graphs; Line graph; Perfect graph; Directed graphs; Graphic methods; Characterization
Año:2013
Volumen:161
Número:13-14
Página de inicio:1925
Página de fin:1942
DOI: http://dx.doi.org/10.1016/j.dam.2013.04.001
Título revista:Discrete Applied Mathematics
Título revista abreviado:Discrete Appl Math
ISSN:0166218X
CODEN:DAMAD
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_0166218X_v161_n13-14_p1925_Bonomo.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v161_n13-14_p1925_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
  • Berge, C., Minimax relations for the partial q-colorings of a graph (1989) Discrete Math., 74, pp. 3-14
  • Berge, C., Chvátal, V., Introduction (1984) Topics on Perfect Graphs, 88. , North-Holland Mathematics Studies Noth-Holland
  • Bonomo, F., Durán, G., Lin, M.C., Szwarcfiter, J.L., On balanced graphs (2006) Math. Program., 105, pp. 233-250
  • Chudnovsky, M., Cornuéjols, G.P., Liu, X., Seymour, P.D., Vušković, K., Recognizing Berge graphs (2005) Combinatorica, 25, pp. 143-186
  • Chudnovsky, M., Robertson, N., Seymour, P.D., Thomas, R., The strong perfect graph theorem (2006) Ann. of Math., 164, pp. 51-229
  • Chvátal, V., On certain polytopes associated with graphs (1975) J. Combin. Theory Ser. B, 18, pp. 138-154
  • Cournier, A., Habib, M., A new linear algorithm for modular decomposition (1994) Proc. 19th International Colloquium on Trees in Algebra and Programming, 787, pp. 68-84. , S. Tison, CAAP'94, Edinburgh, U.K., April 1994 Lect. Notes Comput. Sci. Springer
  • Fulkerson, D.R., Hoffman, A.J., Oppenheim, R., On balanced matrices (1974) Pivoting and Extensions: In Honor of A.W. Tucker, 1, pp. 120-133. , M. Balinski, Mathematical Programming Study North-Holland Amsterdam
  • Golumbic, M.C., Trivially perfect graphs (1978) Discrete Math., 24, pp. 105-107
  • Habib, M., De Montgolfier, F., Paul, C., (2003) A Simple Linear-time Modular Decomposition Algorithm, Technical Report RR-LIRMM-03007, LIRMM, , Université de Montpellier 2 Montepellier, France
  • Hammer, P.L., Difference graphs (1990) Discrete Appl. Math., 28, pp. 35-44
  • Heggernes, P., Kratsch, D., Linear-time certifying recognition algorithms and forbidden induced subgraphs (2007) Nord. J. Comput., 14, pp. 87-108
  • King, A., (2009) Claw-free Graphs and Two Conjectures on Omega, Delta, and Chi, , Ph.D. Thesis, School of Computer Science, McGill University, Montreal, Canada
  • Kloks, T., Kratsch, D., Müller, H., Dominoes (1995) Proc. 20th International Workshop on Graph-Theoretic Concepts in Computer Science, 903, pp. 106-120. , E.W. Mayr, G. Schmidt, G. Tinhofer, WG'94, Herrshing, Germany, June 1994 Lect. Notes Comput. Sci. Springer
  • Konig, D., Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre (1916) Math. Ann., 77, pp. 453-465
  • Konig, D., Graphok és Matrixok (1931) Mat. Fiz. Lapok, 38, pp. 116-119
  • Lehot, P.G.H., An optimal algorithm to detect a line graph and output its root graph (1974) J. ACM, 21, pp. 569-575
  • Lin, M.C., Szwarcfiter, J.L., Faster recognition of clique-Helly and hereditary clique-Helly graphs (2007) Inform. Process. Lett., 3, pp. 40-43
  • Lovász, L., Normal hypergraphs and the perfect graph conjecture (1972) Discrete Math., 2, pp. 253-267
  • Lozin, V.V., E-free bipartite graphs (2000) Diskretn. Anal. Issled. Oper. Ser. 1, 7, pp. 49-66. , (in Russian)
  • McConnell, R.M., Spinrad, J.P., Modular decomposition and transitive orientation (1999) Discrete Math., 201, pp. 189-241
  • Prisner, E., Hereditary clique-Helly graphs (1993) J. Combin. Math. Combin. Comput., 14, pp. 216-220
  • Roussopoulos, N.D., A max m, n algorithm for determining the graph H from its line graph G (1973) Inform. Process. Lett., 2, pp. 108-112
  • Tarjan, R.E., Depth-first search and linear graph algorithms (1972) SIAM J. Comput., 1, pp. 146-160
  • Trotter, L.E., Line perfect graphs (1977) Math. Program., 12, pp. 255-259
  • Tsukiyama, S., Idle, M., Ariyoshi, H., Shirakawa, Y., A new algorithm for generating all the maximal independent sets (1977) SIAM J. Comput., 6, pp. 505-517
  • Wallis, W.D., Zhang, G.H., On maximal clique irreducible graphs (1990) J. Combin. Math. Combin. Comput., 8, pp. 187-193
  • Yannakakis, M., The complexity of the partial order dimension problem (1982) SIAM J. Algebr. Discrete Methods, 3, pp. 351-358
  • Zambelli, G., A polynomial recognition algorithm for balanced matrices (2005) J. Combin. Theory Ser. B, 95, pp. 49-67

Citas:

---------- APA ----------
Bonomo, F., Durán, G., Safe, M.D. & Wagler, A.K. (2013) . On minimal forbidden subgraph characterizations of balanced graphs. Discrete Applied Mathematics, 161(13-14), 1925-1942.
http://dx.doi.org/10.1016/j.dam.2013.04.001
---------- CHICAGO ----------
Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K. "On minimal forbidden subgraph characterizations of balanced graphs" . Discrete Applied Mathematics 161, no. 13-14 (2013) : 1925-1942.
http://dx.doi.org/10.1016/j.dam.2013.04.001
---------- MLA ----------
Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K. "On minimal forbidden subgraph characterizations of balanced graphs" . Discrete Applied Mathematics, vol. 161, no. 13-14, 2013, pp. 1925-1942.
http://dx.doi.org/10.1016/j.dam.2013.04.001
---------- VANCOUVER ----------
Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K. On minimal forbidden subgraph characterizations of balanced graphs. Discrete Appl Math. 2013;161(13-14):1925-1942.
http://dx.doi.org/10.1016/j.dam.2013.04.001