Artículo

Bonomo, F.; Durán, G.; Safe, M.D.; Wagler, A.K. "Clique-perfectness and balancedness of some graph classes" (2014) International Journal of Computer Mathematics. 91(10):2118-2141
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

A graph is clique-perfect if the maximum size of a clique-independent set (a set of pairwise disjoint maximal cliques) and the minimum size of a clique-transversal set (a set of vertices meeting every maximal clique) coincide for each induced subgraph. A graph is balanced if its clique-matrix contains no square submatrix of odd size with exactly two ones per row and column. In this work, we give linear-time recognition algorithms and minimal forbidden induced subgraph characterizations of clique-perfectness and balancedness of P4-tidy graphs and a linear-time algorithm for computing a maximum clique-independent set and a minimum clique-transversal set for any P4-tidy graph. We also give a minimal forbidden induced subgraph characterization and a linear-time recognition algorithm for balancedness of paw-free graphs. Finally, we show that clique-perfectness of diamond-free graphs can be decided in polynomial time by showing that a diamond-free graph is clique-perfect if and only if it is balanced. © 2014, © 2014 Taylor & Francis.

Registro:

Documento: Artículo
Título:Clique-perfectness and balancedness of some graph classes
Autor:Bonomo, F.; Durán, G.; Safe, M.D.; Wagler, A.K.
Filiación:CONICET and Departamento de Computación, FCEN, Universidad de Buenos Aires, Buenos Aires, Argentina
CONICET, Instituto de Cálculo, and Departamento de Matemática, FCEN, Universidad de Buenos Aires, Buenos Aires, Argentina
Departamento de Ingeniería Industrial, FCFM, Universidad de Chile, Santiago de Chile, Chile
Instituto de Ciencias, Universidad Nacional de General Sarmiento, Los Polvorines, Argentina
CNRS and LIMOS, UFR Sciences et Techniques, Université Blaise Pascal, Aubiére, France
Palabras clave:balanced graphs; clique-perfect graphs; diamond-free graphs; P4-tidy graphs; paw-free graphs; recognition algorithms; Clustering algorithms; Diamonds; Graphic methods; Polynomial approximation; Balanced graphs; Diamond-free graphs; Free graphs; Perfect graph; Recognition algorithm; Graph theory
Año:2014
Volumen:91
Número:10
Página de inicio:2118
Página de fin:2141
DOI: http://dx.doi.org/10.1080/00207160.2014.881994
Título revista:International Journal of Computer Mathematics
Título revista abreviado:Int J Comput Math
ISSN:00207160
CODEN:IJCMA
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00207160_v91_n10_p2118_Bonomo

Referencias:

  • Balachandran, V., Nagavamsi, P., Pandu Rangan, C., Clique transversal and clique independence on comparability graphs (1996) Inf. Process. Lett, 58, pp. 181-184
  • Baumann, S., A linear algorithm for the homogeneous decomposition of graphs (1996), Report TUM M9615, Fakultät für Mathematik, Technische Universität München, Munich, Germany; 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., Chvátal, V., Introduction, in Topics on Perfect Graphs (1984) North-Holland Mathematics Studies, 88, pp. vii–xiv. , Berge C., Chvátal V., (eds), Noth-Holland, Amsterdam:
  • Berge, C., Las Vergnas, M., Sur un théorème du type König pour hypergraphes (1970) Ann. N.Y. Acad. Sci, 175, pp. 32-40
  • Bonomo, F., On subclasses and variations of perfect graphs (2005), Doctoral dissertation, Departamento de Computación, FCEyN, Universidad de Buenos Aires, Buenos Aires, Argentina; Bonomo, F., Durán, G., Groshaus, M., Szwarcfiter, J.L., On clique-perfect and K-perfect graphs (2006) Ars Combin, 80, pp. 97-112
  • Bonomo, F., Durán, G., Lin, M.C., Szwarcfiter, J.L., On balanced graphs (2006) Math. Program, 105, pp. 233-250
  • Bonomo, F., Chudnovsky, M., Durán, G., Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs (2008) Discret. Appl. Math, 156, pp. 1058-1082
  • Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K., On minimal forbidden subgraph characterizations of balanced graphs (2009) Electron. Notes Discret. Math, 35, pp. 41-46
  • Bonomo, F., Durán, G., Soulignac, F., Sueiro, G., Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs (2009) Discret. Appl. Math, 157, pp. 3511-3518
  • Bonomo, F., Chudnovsky, M., Durán, G., Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs (2009) Discret. Math, 309, pp. 3485-3499
  • Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K., Balancedness of some subclasses of circular-arc graphs (2010) Electron. Notes Discret. Math, 36, pp. 1121-1128
  • Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K., Clique-perfectness of complements of line graphs (2011) Electron. Notes Discret. Math, 37, pp. 327-332
  • Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K., On minimal forbidden subgraph characterizations of balanced graphs (2013) Discret. Appl. Math, 161, pp. 1925-1942
  • Brandstädt, A., Chepoi, V.D., Dragan, F.F., Clique r-domination and clique r-packing problems on dually chordal graphs (1997) SIAM J. Discret. Math, 10, pp. 109-127
  • Buer, B., Möhring, R.H., A fast algorithm for the decomposition of graphs and posets (1983) Math. Oper. Res, 8, pp. 170-184
  • Chang, M., Farber, M., Tuza, Z., Algorithmic aspects of neighbourhood numbers (1993) SIAM J. Discret. Math, 6, pp. 24-29
  • Chang, M.S., Hsieh, S.Y., Chen, G.H., Dynamic programming on distance-hereditary graphs, in Algorithms and Computation (1997) Lecture Notes Computer Science, 1350, pp. 344-353. , Leong H.W., Imai H., Jain S., (eds), 8th International Symposium, ISAAC ’97, Singapore, December 17–19, 1997, Proceedings, Springer, Berlin:
  • 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. Math, 164, pp. 51-229
  • Chvátal, V., On certain polytopes associated with graphs (1975) J. Combin. Theory Ser. B, 18, pp. 138-154
  • Corneil, D., Perl, Y., Stewart, L., Cographs: Recognition, applications and algorithms (1984) Congr. Numer, 43, pp. 249-258
  • Corneil, D.G., Lerchs, H., Stewart Burlingham, L., Complement reducible graphs (1981) Discret. Appl. Math, 3, pp. 163-174
  • Corneil, D.G., Perl, Y., Stewart, L.K., A linear recognition algorithm for cographs (1985) SIAM J. Comput, 14, pp. 926-934
  • Courcelle, B., A multivariate interlace polynomial and its computation for graphs of bounded clique-width (2008) Electron. J. Comb, 15
  • Courcelle, B., Makowsky, J.A., Rotics, U., Linear time solvable optimization problems on graphs of bounded clique-width (2000) Theory Comput. Syst, 33, pp. 125-150
  • Cournier, A., Habib, M., A new linear algorithm for modular decomposition, in Trees in Algebra and Programming - CAAP’94 (1994) Lecture Notes Computer Science, 787, pp. 68-84. , Tison S., (ed), 19th International Colloquium, Edinburgh, UK, April 11–13, 1994, Proceedings, Springer, Berlin:
  • Dahlhaus, E., Manuel, P.D., Miller, M., Maximum h-colourable subgraph problem in balanced graphs (1998) Inf. Process. Lett, 65, pp. 301-303
  • Dahlhaus, E., Gustedt, J., McConnell, R.M., Efficient and practical algorithms for sequential modular decomposition (2001) J. Algorithms, 41, pp. 360-387
  • Durán, G., Lin, M.C., Szwarcfiter, J.L., On clique-transversal and clique-independent sets (2002) Ann. Oper. Res, 116, pp. 71-77
  • Durán, G., Lin, M.C., Mera, S., Szwarcfiter, J.L., Algorithms for clique-independent sets on subclasses of circular-arc graphs (2006) Discret. Appl. Math, 154, pp. 1783-1790
  • Durán, G., Lin, M.C., Mera, S., Szwarcfiter, J.L., Algorithms for finding clique-transversals of graphs (2008) Ann. Oper. Res, 157, pp. 37-45
  • Edmonds, J., Paths, trees, and flowers (1965) Can. J. Math, 17, pp. 449-467
  • Egerváry, J., Matrixok kombinatorikus tulajdonságairól (1931) Mat. Fiz. Lapok, 38, pp. 16-28
  • Erdős, P., Gallai, T., Tuza, Z., Covering the cliques of a graph with vertices (1992) Discret. Math, 108, pp. 279-289
  • Farber, M., Characterizations of strongly chordal graphs (1983) Discret. Math, 43, pp. 173-189
  • Fouquet, J.L., Giakoumakis, V., On semi-P4-sparse graphs (1997) Discret. Math, pp. 277-300
  • Frick, M., Grohe, M., The complexity of first-order and monadic second-order logic revisited (2004) Ann. Pure Appl. Logic, 130, pp. 3-31
  • Fulkerson, D.R., Hoffman, A.J., Oppenheim, R., On balanced matrices, in Pivoting and Extensions: In Honor of A.W. Tucker (1974) Mathematical Programming Study, 1, pp. 120-133. , Balinski M., (ed), North-Holland, Amsterdam:
  • Gabow, H., Tarjan, R., Faster scaling algorithms for general graph-matching problems (1991) J. ACM, 38, pp. 815-853
  • Gallai, T., Transitiv orientierbare Graphen (1967) Acta Math. Acad. Sci. Hung, 18, pp. 25-66
  • Giakoumakis, V., Roussel, F., Thuillier, H., On P4-tidy graphs (1997) Discret. Math. Theor. Comput. Sci, 1, pp. 17-41
  • Golumbic, M.C., Trivially perfect graphs (1978) Discret. Math, 24, pp. 105-107
  • Guruswami, V., Pandu Rangan, C., Algorithmic aspects of clique-transversal and clique-independent sets (2000) Discret. Appl. Math, 100, pp. 183-202
  • Hoàng, C.T., Perfect graphs (1985), Ph.D. thesis, School of Computer Science, McGill University, Montreal, Canada; Jamison, B., Olariu, S., A new class of brittle graphs (1989) Stud. Appl. Math, 81, pp. 89-92
  • Jamison, B., Olariu, S., On a unique tree representation for P4-extendible graphs (1991) Discret. Appl. Math, 34, pp. 151-164
  • Kőnig, D., Graphok és Matrixok (1931) Mat. Fiz. Lapok, 38, pp. 116-119
  • Lee, C.M., Chang, M.S., Distance-hereditary graphs are clique-perfect (2006) Discret. Appl. Math, 154, pp. 525-536
  • Lehel, J., Tuza, Z., Neighborhood perfect graphs (1986) Discret. Math, 61, pp. 93-101
  • McConnell, R.M., Spinrad, J.P., Modular decomposition and transitive orientation (1999) Discret. Math, 201, pp. 189-241
  • Meyniel, H., The graphs whose odd cycles have at least two chords, in Topics on Perfect Graphs (1984) North-Holland Mathematics Studies, 88, pp. 115-119. , Berge C., Chvátal V., (eds), Noth-Holland, Amsterdam:
  • Olariu, S., Paw-free graphs (1988) Inf. Process. Lett, 28, pp. 53-54
  • Parthasarathy, K., Ravindra, G., The strong perfect-graph conjecture is true for K1, 3-free graphs (1976) J. Combin. Theory Ser. B, 21, pp. 212-223
  • Prisner, E., Hereditary clique-Helly graphs (1993) J. Combin. Math. Combin. Comput, 14, pp. 216-220
  • Sandeep, R.B., Perfectly colorable graphs (2011) Inf. Process. Lett, 111, pp. 960-961
  • Seinsche, D., On a property of the class of n-colorable graphs (1974) J. Combin. Theory Ser. B, 16, pp. 191-193
  • Tedder, M., Corneil1, D., Habib, M., Paul, C., Simpler linear-time modular decomposition via recursive factorizing permutations, in Automata, Languages and Programming (2008) Lecture Notes Computer Science, 5125. , Aceto L., Damgård I., Goldberg L.A., Halldórsson M.M., Ingólfsdóttir A., Walukiewicz I., (eds), 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008, Proceedings, Part I, Springer, Berlin:
  • 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
  • Tucker, A., The strong perfect graph conjecture for planar graphs (1973) Can. J. Math, 25, pp. 103-114
  • Tucker, A., Coloring perfect (K4−e)-free graphs (1987) J. Combin. Theory Ser. B, 42, pp. 313-318
  • West, D.B., (2001) Introduction to Graph Theory, , 2nd ed., Prentice-Hall, Upper Saddle River, NJ:
  • 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. (2014) . Clique-perfectness and balancedness of some graph classes. International Journal of Computer Mathematics, 91(10), 2118-2141.
http://dx.doi.org/10.1080/00207160.2014.881994
---------- CHICAGO ----------
Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K. "Clique-perfectness and balancedness of some graph classes" . International Journal of Computer Mathematics 91, no. 10 (2014) : 2118-2141.
http://dx.doi.org/10.1080/00207160.2014.881994
---------- MLA ----------
Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K. "Clique-perfectness and balancedness of some graph classes" . International Journal of Computer Mathematics, vol. 91, no. 10, 2014, pp. 2118-2141.
http://dx.doi.org/10.1080/00207160.2014.881994
---------- VANCOUVER ----------
Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K. Clique-perfectness and balancedness of some graph classes. Int J Comput Math. 2014;91(10):2118-2141.
http://dx.doi.org/10.1080/00207160.2014.881994