Clique-perfectness and balancedness of some graph classes

References

• V. Balachandran, P. Nagavamsi, and C. Pandu Rangan, Clique transversal and clique independence on comparability graphs, Inf. Process. Lett. 58 (1996), pp. 181–184. doi: 10.1016/0020-0190(96)00054-3
   Web of Science ®Google Scholar
• S. Baumann, A linear algorithm for the homogeneous decomposition of graphs, Report TUM M9615, Fakultät für Mathematik, Technische Universität München, Munich, Germany, 1996.
   Google Scholar
• C. Berge, Färbung von Graphen, deren sämtliche beziehungsweise, deren ungerade Kreise starr sind (Zusammenfassung), Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturwiss. Reihe 10 (1961), pp. 114–115.
   Google Scholar
• C. Berge, Balanced matrices, Math. Program. 2 (1972), pp. 19–31. doi: 10.1007/BF01584535
   Google Scholar
• C. Berge and V. Chvátal, Introduction, in Topics on Perfect Graphs, North-Holland Mathematics Studies, Vol. 88, C. Berge and V. Chvátal, eds., Noth-Holland, Amsterdam, 1984, pp. vii–xiv.
   Google Scholar
• C. Berge and M. Las Vergnas, Sur un théorème du type König pour hypergraphes, Ann. N.Y. Acad. Sci. 175 (1970), pp. 32–40.
   Web of Science ®Google Scholar
• F. Bonomo, On subclasses and variations of perfect graphs, Doctoral dissertation, Departamento de Computación, FCEyN, Universidad de Buenos Aires, Buenos Aires, Argentina, 2005.
   Google Scholar
• F. Bonomo, G. Durán, M. Groshaus, and J.L. Szwarcfiter, On clique-perfect and K-perfect graphs, Ars Combin. 80 (2006), pp. 97–112.
   Web of Science ®Google Scholar
• F. Bonomo, G. Durán, M.C. Lin, and J.L. Szwarcfiter, On balanced graphs, Math. Program. 105 (2006), pp. 233–250. doi: 10.1007/s10107-005-0651-y
   Web of Science ®Google Scholar
• F. Bonomo, M. Chudnovsky, and G. Durán, Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs, Discret. Appl. Math. 156 (2008), pp. 1058–1082. doi: 10.1016/j.dam.2007.05.048
   Web of Science ®Google Scholar
• F. Bonomo, G. Durán, M.D. Safe, and A.K. Wagler, On minimal forbidden subgraph characterizations of balanced graphs, Electron. Notes Discret. Math. 35 (2009), pp. 41–46. doi: 10.1016/j.endm.2009.11.008
   Google Scholar
• F. Bonomo, G. Durán, F. Soulignac, and G. Sueiro, Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs, Discret. Appl. Math. 157 (2009), pp. 3511–3518. doi: 10.1016/j.dam.2009.03.017
   Web of Science ®Google Scholar
• F. Bonomo, M. Chudnovsky, and G. Durán, Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs, Discret. Math. 309 (2009), pp. 3485–3499. doi: 10.1016/j.disc.2007.12.054
   Web of Science ®Google Scholar
• F. Bonomo, G. Durán, M.D. Safe, and A.K. Wagler, Balancedness of some subclasses of circular-arc graphs, Electron. Notes Discret. Math. 36 (2010), pp. 1121–1128. doi: 10.1016/j.endm.2010.05.142
   Google Scholar
• F. Bonomo, G. Durán, M.D. Safe, and A.K. Wagler, Clique-perfectness of complements of line graphs, Electron. Notes Discret. Math. 37 (2011), pp. 327–332. doi: 10.1016/j.endm.2011.05.056
   Google Scholar
• F. Bonomo, G. Durán, M.D. Safe, and A.K. Wagler, On minimal forbidden subgraph characterizations of balanced graphs, Discret. Appl. Math. 161 (2013), pp. 1925–1942. doi: 10.1016/j.dam.2013.04.001
   Web of Science ®Google Scholar
• A. Brandstädt, V.D. Chepoi, and F.F. Dragan, Clique r-domination and clique r-packing problems on dually chordal graphs, SIAM J. Discret. Math. 10 (1997), pp. 109–127. doi: 10.1137/S0895480194267853
   Web of Science ®Google Scholar
• B. Buer and R.H. Möhring, A fast algorithm for the decomposition of graphs and posets, Math. Oper. Res. 8 (1983), pp. 170–184. doi: 10.1287/moor.8.2.170
   Web of Science ®Google Scholar
• M. Chang, M. Farber, and Z. Tuza, Algorithmic aspects of neighbourhood numbers, SIAM J. Discret. Math. 6 (1993), pp. 24–29. doi: 10.1137/0406002
   Web of Science ®Google Scholar
• M.S. Chang, S.Y. Hsieh, and G.H. Chen, Dynamic programming on distance-hereditary graphs, in Algorithms and Computation, 8th International Symposium, ISAAC ’97, Singapore, December 17–19, 1997, Proceedings, Lecture Notes Computer Science, Vol. 1350, H.W. Leong, H. Imai, and S. Jain, eds., Springer, Berlin, 1997, pp. 344–353. doi: 10.1007/3-540-63890-3_37
   Google Scholar
• M. Chudnovsky, G.P. Cornuéjols, X. Liu, P.D. Seymour, and K. Vušković, Recognizing Berge graphs, Combinatorica 25 (2005), pp. 143–186. doi: 10.1007/s00493-005-0012-8
   Web of Science ®Google Scholar
• M. Chudnovsky, N. Robertson, P.D. Seymour, and R. Thomas, The strong perfect graph theorem, Ann. Math. 164 (2006), pp. 51–229. doi: 10.4007/annals.2006.164.51
   Web of Science ®Google Scholar
• V. Chvátal, On certain polytopes associated with graphs, J. Combin. Theory Ser. B 18 (1975), pp. 138–154. doi: 10.1016/0095-8956(75)90041-6
   Web of Science ®Google Scholar
• D. Corneil, Y. Perl, and L. Stewart, Cographs: Recognition, applications and algorithms, Congr. Numer. 43 (1984), pp. 249–258.
   Google Scholar
• D.G. Corneil, H. Lerchs, and L. Stewart Burlingham, Complement reducible graphs, Discret. Appl. Math. 3 (1981), pp. 163–174. doi: 10.1016/0166-218X(81)90013-5
   Web of Science ®Google Scholar
• D.G. Corneil, Y. Perl, and L.K. Stewart, A linear recognition algorithm for cographs, SIAM J. Comput. 14 (1985), pp. 926–934. doi: 10.1137/0214065
   Web of Science ®Google Scholar
• B. Courcelle, A multivariate interlace polynomial and its computation for graphs of bounded clique-width, Electron. J. Comb. 15 (2008), # R69.
   Web of Science ®Google Scholar
• B. Courcelle, J.A. Makowsky, and U. Rotics, Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst. 33 (2000), pp. 125–150. doi: 10.1007/s002249910009
   Web of Science ®Google Scholar
• A. Cournier and M. Habib, A new linear algorithm for modular decomposition, in Trees in Algebra and Programming - CAAP’94, 19th International Colloquium, Edinburgh, UK, April 11–13, 1994, Proceedings, Lecture Notes Computer Science, Vol. 787, S. Tison, ed., Springer, Berlin, 1994, pp. 68–84. doi: 10.1007/BFb0017474
   Google Scholar
• E. Dahlhaus, P.D. Manuel, and M. Miller, Maximum h-colourable subgraph problem in balanced graphs, Inf. Process. Lett. 65 (1998), pp. 301–303. doi: 10.1016/S0020-0190(98)00019-2
   Web of Science ®Google Scholar
• E. Dahlhaus, J. Gustedt, and R.M. McConnell, Efficient and practical algorithms for sequential modular decomposition, J. Algorithms 41 (2001), pp. 360–387. doi: 10.1006/jagm.2001.1185
   Web of Science ®Google Scholar
• G. Durán, M.C. Lin, and J.L. Szwarcfiter, On clique-transversal and clique-independent sets, Ann. Oper. Res. 116 (2002), pp. 71–77. doi: 10.1023/A:1021363810398
   Web of Science ®Google Scholar
• G. Durán, M.C. Lin, S. Mera, and J.L. Szwarcfiter, Algorithms for clique-independent sets on subclasses of circular-arc graphs, Discret. Appl. Math. 154 (2006), pp. 1783–1790. doi: 10.1016/j.dam.2006.03.022
   Web of Science ®Google Scholar
• G. Durán, M.C. Lin, S. Mera, and J.L. Szwarcfiter, Algorithms for finding clique-transversals of graphs, Ann. Oper. Res. 157 (2008), pp. 37–45. doi: 10.1007/s10479-007-0189-x
   Web of Science ®Google Scholar
• J. Edmonds, Paths, trees, and flowers, Can. J. Math. 17 (1965), pp. 449–467. doi: 10.4153/CJM-1965-045-4
   Web of Science ®Google Scholar
• J. Egerváry, Matrixok kombinatorikus tulajdonságairól, Mat. Fiz. Lapok 38 (1931), pp. 16–28.
   Google Scholar
• P. Erdős, T. Gallai, and Z. Tuza, Covering the cliques of a graph with vertices, Discret. Math. 108 (1992), pp. 279–289. doi: 10.1016/0012-365X(92)90681-5
   Web of Science ®Google Scholar
• M. Farber, Characterizations of strongly chordal graphs, Discret. Math. 43 (1983), pp. 173–189. doi: 10.1016/0012-365X(83)90154-1
   Web of Science ®Google Scholar
• J.L. Fouquet and V. Giakoumakis, On semi-P4-sparse graphs, Discret. Math. 165–166 (1997), pp. 277–300.
   Web of Science ®Google Scholar
• M. Frick and M. Grohe, The complexity of first-order and monadic second-order logic revisited, Ann. Pure Appl. Logic 130 (2004), pp. 3–31. doi: 10.1016/j.apal.2004.01.007
   Web of Science ®Google Scholar
• D.R. Fulkerson, A.J. Hoffman, and R. Oppenheim, On balanced matrices, in Pivoting and Extensions: In Honor of A.W. Tucker, Mathematical Programming Study, Vol. 1, M. Balinski, ed., North-Holland, Amsterdam, 1974, pp. 120–133.
   Google Scholar
• H. Gabow and R. Tarjan, Faster scaling algorithms for general graph-matching problems, J. ACM 38 (1991), pp. 815–853. doi: 10.1145/115234.115366
   Web of Science ®Google Scholar
• T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hung. 18 (1967), pp. 25–66. doi: 10.1007/BF02020961
   Web of Science ®Google Scholar
• V. Giakoumakis, F. Roussel, and H. Thuillier, On P4-tidy graphs, Discret. Math. Theor. Comput. Sci. 1 (1997), pp. 17–41.
   Google Scholar
• M.C. Golumbic, Trivially perfect graphs, Discret. Math. 24 (1978), pp. 105–107. doi: 10.1016/0012-365X(78)90178-4
   Web of Science ®Google Scholar
• V. Guruswami and C. Pandu Rangan, Algorithmic aspects of clique-transversal and clique-independent sets, Discret. Appl. Math. 100 (2000), pp. 183–202. doi: 10.1016/S0166-218X(99)00159-6
   Web of Science ®Google Scholar
• C.T. Hoàng, Perfect graphs, Ph.D. thesis, School of Computer Science, McGill University, Montreal, Canada, 1985.
   Google Scholar
• B. Jamison and S. Olariu, A new class of brittle graphs, Stud. Appl. Math. 81 (1989), pp. 89–92.
   Web of Science ®Google Scholar
• B. Jamison and S. Olariu, On a unique tree representation for P4-extendible graphs, Discret. Appl. Math. 34 (1991), pp. 151–164. doi: 10.1016/0166-218X(91)90085-B
   Web of Science ®Google Scholar
• D. Kőnig, Graphok és Matrixok, Mat. Fiz. Lapok 38 (1931), pp. 116–119.
   Google Scholar
• C.M. Lee and M.S. Chang, Distance-hereditary graphs are clique-perfect, Discret. Appl. Math. 154 (2006), pp. 525–536. doi: 10.1016/j.dam.2005.07.011
   Web of Science ®Google Scholar
• J. Lehel and Z. Tuza, Neighborhood perfect graphs, Discret. Math. 61 (1986), pp. 93–101. doi: 10.1016/0012-365X(86)90031-2
   Web of Science ®Google Scholar
• R.M. McConnell and J.P. Spinrad, Modular decomposition and transitive orientation, Discret. Math. 201 (1999), pp. 189–241. doi: 10.1016/S0012-365X(98)00319-7
   Web of Science ®Google Scholar
• H. Meyniel, The graphs whose odd cycles have at least two chords, in Topics on Perfect Graphs, North-Holland Mathematics Studies, Vol. 88, C. Berge and V. Chvátal, eds., Noth-Holland, Amsterdam, 1984, pp. 115–119. doi: 10.1016/S0304-0208(08)72927-X
   Google Scholar
• S. Olariu, Paw-free graphs, Inf. Process. Lett. 28 (1988), pp. 53–54. doi: 10.1016/0020-0190(88)90143-3
   Web of Science ®Google Scholar
• K. Parthasarathy and G. Ravindra, The strong perfect-graph conjecture is true for K1, 3-free graphs, J. Combin. Theory Ser. B 21 (1976), pp. 212–223. doi: 10.1016/S0095-8956(76)80005-6
   Web of Science ®Google Scholar
• E. Prisner, Hereditary clique-Helly graphs, J. Combin. Math. Combin. Comput. 14 (1993), pp. 216–220.
   Google Scholar
• R.B. Sandeep, Perfectly colorable graphs, Inf. Process. Lett. 111 (2011), pp. 960–961. doi: 10.1016/j.ipl.2011.07.001
   Web of Science ®Google Scholar
• D. Seinsche, On a property of the class of n-colorable graphs, J. Combin. Theory Ser. B 16 (1974), pp. 191–193. doi: 10.1016/0095-8956(74)90063-X
   Google Scholar
• M. Tedder, D. Corneil1, M. Habib, and C. Paul, Simpler linear-time modular decomposition via recursive factorizing permutations, in Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008, Proceedings, Part I, Lecture Notes Computer Science, Vol. 5125, L. Aceto, I. Damgård, L.A. Goldberg, M.M. Halldórsson, A. Ingólfsdóttir, and I. Walukiewicz, eds., Springer, Berlin, 2008.
   Google Scholar
• S. Tsukiyama, M. Idle, H. Ariyoshi, and Y. Shirakawa, A new algorithm for generating all the maximal independent sets, SIAM J. Comput. 6 (1977), pp. 505–517. doi: 10.1137/0206036
   Google Scholar
• A. Tucker, The strong perfect graph conjecture for planar graphs, Can. J. Math. 25 (1973), pp. 103–114. doi: 10.4153/CJM-1973-009-3
   Web of Science ®Google Scholar
• A. Tucker, Coloring perfect (K4−e)-free graphs, J. Combin. Theory Ser. B 42 (1987), pp. 313–318. doi: 10.1016/0095-8956(87)90048-7
   Web of Science ®Google Scholar
• D.B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, Upper Saddle River, NJ, 2001.
   Google Scholar
• G. Zambelli, A polynomial recognition algorithm for balanced matrices, J. Combin. Theory Ser. B 95 (2005), pp. 49–67. doi: 10.1016/j.jctb.2005.02.006
   Web of Science ®Google Scholar