×

Characterization and recognition of generalized clique-Helly graphs. (English) Zbl 1143.05071

For given \(p\geq 1\), \(q\geq 0\) a family of sets \(\mathcal F\) is \((p,q)\)-intersecting if every subfamily \(\mathcal F'\subseteq \mathcal F\) consisting of \(p\) or less members has total intersection cardinality at least \(q\). A family of sets \(\mathcal F\) is \((p,q)\)-Helly if every \((p,q)\)-intersecting subfamily \(\mathcal F'\subseteq \mathcal F\) has total intersection cardinality at least \(q\). A graph \(G\) is \((p,q)\)-clique-Helly if its family of (maximal) cliques is \((p,q)\)-Helly.
This generalizes the notion of the Helly property and the clique-Helly graphs which correspond to the case when \(p=2\), \(q=1\). A characterization of \((p,q)\)-clique-Helly graphs is given. It is shown that for fixed \(p,q\) a polynomial-time recognition algorithm exists while for a variable \(p\) or \(q\) the recognition of \((p,q)\)-clique-Helly graphs is NP-hard.

MSC:

05C75 Structural characterization of families of graphs
05C62 Graph representations (geometric and intersection representations, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albertson, M. O.; Collins, K. L., Duality and perfection for edges in cliques, J. Combin. Theory Ser. B, 36, 298-309 (1984) · Zbl 0527.05032
[2] Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029
[3] Berge, C., Hypergraphs (1989), Elsevier: Elsevier Amsterdam · Zbl 0334.05117
[4] C. Berge, P. Duchet, A generalization of Gilmore’s theorem, in: M. Fiedler (Ed.), Recent Advances in Graph Theory, Acad. Praha, Prague, 1975, pp. 49-55.; C. Berge, P. Duchet, A generalization of Gilmore’s theorem, in: M. Fiedler (Ed.), Recent Advances in Graph Theory, Acad. Praha, Prague, 1975, pp. 49-55. · Zbl 0325.05125
[5] A. Brandstädt, V.B. Lee, J. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, vol. 3, SIAM, Philadelphia, 1999.; A. Brandstädt, V.B. Lee, J. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, vol. 3, SIAM, Philadelphia, 1999.
[6] P.L. Butzer, R.J. Nessel, E.L. Stark, Eduard Helly (1884-1943): in memoriam, Resultate Math. 7 (1984).; P.L. Butzer, R.J. Nessel, E.L. Stark, Eduard Helly (1884-1943): in memoriam, Resultate Math. 7 (1984).
[7] M.R. Cerioli, Edge-clique graphs, Ph.D. Thesis, Federal University of Rio de Janeiro, 1999 (in Portuguese).; M.R. Cerioli, Edge-clique graphs, Ph.D. Thesis, Federal University of Rio de Janeiro, 1999 (in Portuguese). · Zbl 1075.05572
[8] S.A. Cook, The complexity of theorem-proving procedures, Proceedings of the Third Annual ACM Symposium on Theory of Computing, 1971, New York, pp. 151-158.; S.A. Cook, The complexity of theorem-proving procedures, Proceedings of the Third Annual ACM Symposium on Theory of Computing, 1971, New York, pp. 151-158.
[9] L. Danzer, B. Grünbaum, V.L. Klee, Helly’s theorem and its relatives, Proceedings Symposium on Pure Math AMS, vol .7, 1963, pp. 101-180.; L. Danzer, B. Grünbaum, V.L. Klee, Helly’s theorem and its relatives, Proceedings Symposium on Pure Math AMS, vol .7, 1963, pp. 101-180. · Zbl 0132.17401
[10] Dourado, M. C.; Protti, F.; Szwarcfiter, J. L., Computational aspects of the Helly property: a survey, Journal of the Brazilian Computer Society, 12, 1, 7-33 (2006)
[11] M.C. Dourado, F. Protti, J.L. Szwarcfiter, Characterization and recognition of generalized clique-Helly graphs, Proceedings of WG’2004—30th International Workshop on Graph-Theoretic Concepts in Computer Science, Hölterhoff House, Bad Honeff, Germany, June 2004, Lecture Notes in Computer Science, vol. 3353, Springer, Berlin, 2004, pp. 344-354.; M.C. Dourado, F. Protti, J.L. Szwarcfiter, Characterization and recognition of generalized clique-Helly graphs, Proceedings of WG’2004—30th International Workshop on Graph-Theoretic Concepts in Computer Science, Hölterhoff House, Bad Honeff, Germany, June 2004, Lecture Notes in Computer Science, vol. 3353, Springer, Berlin, 2004, pp. 344-354. · Zbl 1112.05321
[12] F.F. Dragan, Centers of graphs and the Helly property, Doctoral Thesis, Moldava State University, Chisinaˇu, 1989 (in Russian).; F.F. Dragan, Centers of graphs and the Helly property, Doctoral Thesis, Moldava State University, Chisinaˇu, 1989 (in Russian).
[13] Golumbic, M. C.; Jamison, R. E., The edge intersection graphs of paths in a tree, J. Combin. Theory Ser. B, 38, 8-22 (1985) · Zbl 0537.05063
[14] Helly, E., Ueber Mengen konvexer Koerper mit gemeinschaftlichen Punkter, Jahresber, Math. Verein., 32, 175-176 (1923) · JFM 49.0534.02
[15] Prisner, E., Hereditary clique-Helly graphs, J. Combin. Math. Combin. Comput., 14, 216-220 (1993) · Zbl 0794.05113
[16] Prisner, E., Graph Dynamics, Pitman Research Notes in Mathematics, vol. 338 (1995), Longman: Longman London
[17] Protti, F.; Szwarcfiter, J. L., Clique-inverse graphs of \(K_3\)-free and \(K_4\)-free graphs, J. Graph Theory, 35, 257-272 (2000) · Zbl 0966.05055
[18] Szwarcfiter, J. L., Recognizing clique-Helly graphs, Ars Combin., 45, 29-32 (1997) · Zbl 0933.05127
[19] Tuza, Zs., Extremal bi-Helly families, Discrete Math., 213, 321-331 (2000) · Zbl 0943.05057
[20] Voloshin, V. I., On the upper chromatic number of a hypergraph, Austral. J. Combin., 11, 25-45 (1995) · Zbl 0827.05027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.