×

Strong cliques in diamond-free graphs. (English) Zbl 1458.05189

Summary: A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques in the class of diamond-free graphs, from both structural and algorithmic points of view. We show that the following five NP-hard or co-NP-hard problems all remain NP-hard or co-NP-hard when restricted to the class of diamond-free graphs: Is a given clique strong? Does the graph have a strong clique? Is every vertex contained in a strong clique? Given a partition of the vertex set into cliques, is every clique in the partition strong? Can the vertex set be partitioned into strong cliques? On the positive side, we show that the following three problems whose computational complexity is open in general can be solved in polynomial time in the class of diamond-free graphs: Does every induced subgraph have a strong clique? Is every maximal clique strong? Is every edge contained in a strong clique? The last two results are derived from a characterization of diamond-free graphs in which every maximal clique is strong, which also implies an improved Erdős-Hajnal property for such graphs.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alcón, L.; Gutierrez, M.; Kovács, I.; Milanič, M.; Rizzi, R., Strong cliques and equistability of EPT graphs, Discrete Appl. Math., 203, 13-25 (2016) · Zbl 1332.05042
[2] Alcón, L.; Gutierrez, M.; Milanič, M., A characterization of claw-free CIS graphs and new results on the order of CIS graphs, Electron. Notes Theor. Comput. Sci., 346, 15-27 (2019) · Zbl 07515165
[3] Alekseev, V. E., On the number of maximal independent sets in graphs from hereditary classes, (Combinatorial-Algebraic Methods in Discrete Optimization. Combinatorial-Algebraic Methods in Discrete Optimization, University of Nizhny Novgorod (1991)), 5-8, (in Russian)
[4] Anbeek, C.; DeTemple, D.; McAvaney, K.; Robertson, J., When are chordal graphs also partition graphs?, Australas. J. Comb., 16, 285-293 (1997) · Zbl 0884.05076
[5] Andrade, D. V.; Boros, E.; Gurvich, V., Not complementary connected and not CIS d-graphs form weakly monotone families, Discrete Math., 310, 5, 1089-1096 (2010) · Zbl 1213.05219
[6] Andrade, D. V.; Boros, E.; Gurvich, V., On Graphs Whose Maximal Cliques and Stable Sets Intersect, Springer Optim. Appl., vol. 139, 3-63 (2018), Springer: Springer Cham, See also RRR 17-2006, RUTCOR Research Reports, Rutgers University · Zbl 1416.05203
[7] Balas, E.; Yu, C. S., On graphs with polynomially solvable maximum-weight clique problem, Networks, 19, 2, 247-253 (1989) · Zbl 0661.05036
[8] (Berge, C.; Chvátal, V., Topics on Perfect Graphs. Topics on Perfect Graphs, North-Holland Mathematics Studies, vol. 88 (1984), North-Holland Publishing Co.: North-Holland Publishing Co. Amsterdam) · Zbl 0546.00006
[9] Berry, A.; Brandstädt, A.; Giakoumakis, V.; Maffray, F., Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds, Discrete Appl. Math., 184, 50-61 (2015) · Zbl 1311.05182
[10] Bollobás, B.; Brightwell, G. R., Convex bodies, graphs and partial orders, Proc. Lond. Math. Soc. (3), 80, 2, 415-450 (2000) · Zbl 1029.52002
[11] Boros, E.; Gurvich, V.; Milanič, M., On CIS circulants, Discrete Math., 318, 78-95 (2014) · Zbl 1281.05073
[12] Boros, E.; Gurvich, V.; Milanič, M., On equistable, split, CIS, and related classes of graphs, Discrete Appl. Math., 216, part 1, 47-66 (2017) · Zbl 1350.05117
[13] Brandstädt, A.; Giakoumakis, V.; Maffray, F., Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences, Discrete Appl. Math., 160, 4-5, 471-478 (2012) · Zbl 1236.05127
[14] Burlet, M.; Fonlupt, J., Polynomial algorithm to recognize a Meyniel graph, (Topics on Perfect Graphs. Topics on Perfect Graphs, North-Holland Math. Stud., vol. 88 (1984), North-Holland: North-Holland Amsterdam), 225-252 · Zbl 0552.05058
[15] Cheston, G. A.; Hare, E. O.; Hedetniemi, S. T.; Laskar, R. C., Simplicial graphs, vol. 67, (Nineteenth Southeastern Conference on Combinatorics, Graph Theory, and Computing. Nineteenth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Baton Rouge, LA, 1988 (1988)), 105-113 · Zbl 0668.05041
[16] Cheston, G. A.; Jap, T. S., A survey of the algorithmic properties of simplicial, upper bound and middle graphs, J. Graph Algorithms Appl., 10, 2, 159-190 (2006) · Zbl 1161.68648
[17] Chiarelli, N.; Martínez-Barona, B.; Milanič, M.; Monnot, J.; Muršič, P., Strong cliques in diamond-free graphs, (Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci., vol. 12301 (2020), Springer), 261-273 · Zbl 07636211
[18] Chudnovsky, M., The Erdös-Hajnal conjecture—a survey, J. Graph Theory, 75, 2, 178-190 (2014) · Zbl 1280.05086
[19] Chudnovsky, M.; Goedgebeur, J.; Schaudt, O.; Zhong, M., Obstructions for three-coloring graphs without induced paths on six vertices, J. Comb. Theory, Ser. B, 140, 45-83 (2020) · Zbl 1430.05033
[20] Chvátal, V.; Slater, P. J., A note on well-covered graphs, (Quo Vadis, Graph Theory?. Quo Vadis, Graph Theory?, Ann. Discrete Math., vol. 55 (1993), North-Holland: North-Holland Amsterdam), 179-181 · Zbl 0801.68119
[21] Dabrowski, K. K.; Dross, F.; Paulusma, D., Colouring diamond-free graphs, J. Comput. Syst. Sci., 89, 410-431 (2017) · Zbl 1372.05067
[22] Deng, X.; Li, G.; Zang, W., Proof of Chvátal’s conjecture on maximal stable sets and maximal cliques in graphs, J. Comb. Theory, Ser. B, 91, 2, 301-325 (2004) · Zbl 1048.05048
[23] Dobson, E.; Hujdurović, A.; Milanič, M.; Verret, G., Vertex-transitive CIS graphs, Eur. J. Comb., 44, part A, 87-98 (2015) · Zbl 1302.05077
[24] Erdős, P.; Hajnal, A., Ramsey-type theorems, Combinatorics and Complexity, Chicago, IL, 1987. Combinatorics and Complexity, Chicago, IL, 1987, Discrete Appl. Math., 25, 1-2, 37-52 (1989) · Zbl 0715.05052
[25] Fellows, M. R.; Guo, J.; Komusiewicz, C.; Niedermeier, R.; Uhlmann, J., Graph-based data clustering with overlaps, Discrete Optim., 8, 1, 2-17 (2011) · Zbl 1248.90070
[26] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, vol. 57 (2004), Elsevier Science B.V.: Elsevier Science B.V. Amsterdam · Zbl 1050.05002
[27] Golumbic, M. C.; Goss, C. F., Perfect elimination and chordal bipartite graphs, J. Graph Theory, 2, 2, 155-163 (1978) · Zbl 0411.05060
[28] Gurvich, V., On exact blockers and anti-blockers, Δ-conjecture, and related problems, Discrete Appl. Math., 159, 5, 311-321 (2011) · Zbl 1210.05039
[29] Gyárfás, A., Reflections on a problem of Erdős and Hajnal, (The Mathematics of Paul Erdős, II. The Mathematics of Paul Erdős, II, Algorithms Combin., vol. 14 (1997), Springer: Springer Berlin), 93-98 · Zbl 0863.05047
[30] Hoàng, C. T., On a conjecture of Meyniel, J. Comb. Theory, Ser. B, 42, 3, 302-312 (1987) · Zbl 0634.05058
[31] Hoàng, C. T., Efficient algorithms for minimum weighted colouring of some classes of perfect graphs, Discrete Appl. Math., 55, 2, 133-143 (1994) · Zbl 0815.68076
[32] Hougardy, S., Classes of perfect graphs, Discrete Math., 306, 19-20, 2529-2571 (2006) · Zbl 1104.05029
[33] Hujdurović, A.; Milanič, M.; Ries, B., Graphs vertex-partitionable into strong cliques, Discrete Math., 341, 5, 1392-1405 (2018) · Zbl 1383.05239
[34] Hujdurović, A.; Milanič, M.; Ries, B., Detecting strong cliques, Discrete Math., 342, 9, 2738-2750 (2019) · Zbl 1416.05269
[35] Kamiński, M.; Lozin, V., Coloring edges and vertices of graphs without short or long cycles, Contrib. Discrete Math., 2, 1, 61-66 (2007) · Zbl 1188.05065
[36] Karthick, T.; Mishra, S., On the chromatic number of \(( P_6\), diamond)-free graphs, Graphs Comb., 34, 4, 677-692 (2018) · Zbl 1397.05066
[37] Kloks, T.; Lee, C.-M.; Liu, J.; Müller, H., On the recognition of general partition graphs, (Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci., vol. 2880 (2003), Springer: Springer Berlin), 273-283 · Zbl 1255.05160
[38] Kloks, T.; Müller, H.; Vušković, K., Even-hole-free graphs that do not contain diamonds: a structure theorem and its consequences, J. Comb. Theory, Ser. B, 99, 5, 733-800 (2009) · Zbl 1218.05160
[39] König, D., Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Math. Ann., 77, 4, 453-465 (1916) · JFM 46.0146.03
[40] Lehot, P. G.H., An optimal algorithm to detect a line graph and output its root graph, J. Assoc. Comput. Mach., 21, 569-575 (1974) · Zbl 0295.05118
[41] Mahadev, N. V.R.; Peled, U. N.; Sun, F., Equistable graphs, J. Graph Theory, 18, 3, 281-299 (1994) · Zbl 0794.05112
[42] McAvaney, K.; Robertson, J.; DeTemple, D., A characterization and hereditary properties for partition graphs, Discrete Math., 113, 1-3, 131-142 (1993) · Zbl 0771.05084
[43] Milanič, M.; Trotignon, N., Equistarable graphs and counterexamples to three conjectures on equistable graphs, J. Graph Theory, 84, 4, 536-551 (2017) · Zbl 1359.05054
[44] Olariu, S., A decomposition for strongly perfect graphs, J. Graph Theory, 13, 3, 301-311 (1989) · Zbl 0661.05056
[45] Payan, C., A class of threshold and domishold graphs: equistable and equidominating graphs, Discrete Math., 29, 1, 47-52 (1980) · Zbl 0542.05050
[46] Prisner, E., Graphs with few cliques, (Graph Theory, Combinatorics, and Algorithms, Vols. 1, 2. Graph Theory, Combinatorics, and Algorithms, Vols. 1, 2, Kalamazoo, MI, 1992 (1995), Wiley: Wiley New York), 945-956 · Zbl 0844.05062
[47] Ravindra, G., Strongly perfect line graphs and total graphs, (Finite and Infinite Sets, Vol. I, II. Finite and Infinite Sets, Vol. I, II, Eger, 1981. Finite and Infinite Sets, Vol. I, II. Finite and Infinite Sets, Vol. I, II, Eger, 1981, Colloq. Math. Soc. János Bolyai, vol. 37 (1984), North-Holland: North-Holland Amsterdam), 621-633 · Zbl 0579.05055
[48] Roussopoulos, N. D., A max \(\{m, n \}\) algorithm for determining the graph H from its line graph G, Inf. Process. Lett., 2, 108-112 (1973) · Zbl 0274.05116
[49] Sankaranarayana, R. S.; Stewart, L. K., Complexity results for well-covered graphs, Networks, 22, 3, 247-262 (1992) · Zbl 0780.90104
[50] Skowrońska, M.; Sysło, M. M., An algorithm to recognize a middle graph, Discrete Appl. Math., 7, 2, 201-208 (1984) · Zbl 0528.05049
[51] Spinrad, J. P., Finding large holes, Inf. Process. Lett., 39, 4, 227-229 (1991) · Zbl 0735.68069
[52] Tarjan, R. E., Decomposition by clique separators, Discrete Math., 55, 2, 221-232 (1985) · Zbl 0572.05039
[53] Tsukiyama, S.; Ide, M.; Ariyoshi, H.; Shirakawa, I., A new algorithm for generating all the maximal independent sets, SIAM J. Comput., 6, 3, 505-517 (1977) · Zbl 0364.05027
[54] Tucker, A., Coloring perfect \(( K_4 - e)\)-free graphs, J. Comb. Theory, Ser. B, 42, 313-318 (1987) · Zbl 0585.05007
[55] Whitesides, S. H., An algorithm for finding clique cut-sets, Inf. Process. Lett., 12, 1, 31-32 (1981) · Zbl 0454.68078
[56] Whitney, H., Congruent graphs and the connectivity of graphs, Am. J. Math., 54, 1, 150-168 (1932) · JFM 58.0609.01
[57] Zang, W., Generalizations of Grillet’s theorem on maximal stable sets and maximal cliques in graphs, Discrete Math., 143, 1-3, 259-268 (1995) · Zbl 0831.05036
[58] Zverovich, I.; Zverovich, I., Bipartite bihypergraphs: a survey and new results, Discrete Math., 306, 8-9, 801-811 (2006) · Zbl 1093.05046
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.