×

zbMATH — the first resource for mathematics

Distance-hereditary graphs are clique-perfect. (English) Zbl 1110.68108
Summary: We show that the clique-transversal number \(\tau_C(G)\) and the clique-independence number \(\alpha_C(G)\) are equal for any distance-hereditary graph \(G\). As a byproduct of proving that \(\tau_C(G)= \alpha_C(G)\), we give a linear-time algorithm to find a minimum clique-transversal set and a maximum clique-independent set simultaneously for distance-hereditary graphs.
Reviewer: Reviewer (Berlin)

MSC:
68R10 Graph theory (including graph drawing) in computer science
05C12 Distance in graphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andreae, T., On the clique-transversal number of chordal graphs, Discrete math., 191, 3-11, (1998) · Zbl 0955.05058
[2] Andreae, T.; Flotow, C., On covering all cliques of a chordal graph, Discrete math., 149, 299-302, (1996) · Zbl 0846.05050
[3] Andreae, T.; Schughart, M.; Tuza, Zs., Clique transversal sets of line graphs and complements of line graphs, Discrete math., 88, 11-20, (1991) · Zbl 0734.05077
[4] Balachandran, V.; Nagavamsi, P.; Rangan, C.P., Clique transversal and clique independence on comparability graphs, Inform. process. lett., 58, 181-184, (1996)
[5] Bandelt, H.J.; Mulder, H.M., Distance hereditary graphs, J. combin. theory ser. B, 41, 182-208, (1986) · Zbl 0605.05024
[6] Brandstädt, A.; Chepoi, V.D.; Dragan, F.F., Clique \(r\)-domination and clique \(r\)-packing problems on dually chordal graphs, SIAM J. discrete math., 10, 1, 109-127, (1997) · Zbl 0869.05048
[7] Brandstädt, A.; Le, V.B.; Spinrad, J.P., Graph classes—A survey, SIAM monographs on discrete mathematics and applications, (1999), SIAM Philadelphia, PA
[8] Chang, G.J.; Farber, M.; Tuza, Zs., Algorithmic aspects of neighborhood numbers, SIAM J. discrete math., 6, 24-29, (1993) · Zbl 0777.05085
[9] Chang, M.S.; Chen, Y.H.; Chang, G.J.; Yan, J.H., Algorithmic aspects of the generalised clique transversal problem on chordal graphs, Discrete appl. math., 66, 189-203, (1996) · Zbl 0854.68072
[10] M.S. Chang, S.Y. Hsieh, G.H. Chen, Dynamic Programming on Distance-Hereditary Graphs, Lecture Notes in Computer Science, vol. 1350, 1997, Springer, Berlin, pp. 344-353.
[11] M.S. Chang, T. Kloks, C.M. Lee, Maximum clique transversals, in: Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 2204, 2001, Springer, Berlin, pp. 32-43. · Zbl 1042.68619
[12] Courcelle, B.; Engelfriet, J.; Rozenberg, G., Handle-rewriting hypergraph grammars, J. comput. system sci., 46, 218-270, (1993) · Zbl 0825.68446
[13] Courcelle, B.; Olariu, S., Upper bounds to the clique-width of graphs, Discrete appl. math., 101, 77-114, (2000) · Zbl 0958.05105
[14] Dahlhaus, E.; Manuel, P.D.; Miller, M., Maximum \(h\)-colourable subgraph problem in balanced graphs, Inform. process. lett., 65, 301-303, (1998) · Zbl 1338.68098
[15] Durán, G.; Lin, M.C.; Szwarcfiter, J.L., On clique-transversal and clique-independent sets, Ann. oper. res., 116, 71-77, (2002) · Zbl 1013.90107
[16] Eades, P.; Keil, M.; Manuel, P.D.; Miller, M., Two minimum dominating sets with minimum intersection in chordal graphs, Nordic J. comput., 3, 220-237, (1996)
[17] Erdös, P.; Gallai, T.; Tuza, Zs., Covering the cliques of a graph with vertices, Discrete math., 108, 279-289, (1992) · Zbl 0766.05063
[18] Golumbicm, M.C.; Rotics, U., On the clique-width of some perfect graph classes, Int. J. foundations comput. sci., 11, 3, 423-443, (2000) · Zbl 1320.05090
[19] Guruswami, V.; Rangan, C.P., Algorithmic aspects of clique-transversal and clique-independent sets, Discrete appl. math., 100, 183-202, (2000) · Zbl 0948.68135
[20] Hammer, P.L.; Maffray, F., Completely separable graphs, Discrete appl. math., 27, 85-90, (1990) · Zbl 0694.05060
[21] C.M. Lee, M.S. Chang, S.C. Sheu, The clique transversal and clique independence of distance hereditary graphs, in: Proceedings of the 19th Workshop on Combinatorial Mathematics and Computation Theory, Taiwan, 2002, pp. 64-69.
[22] Lehel, J.; Tuza, Zs., Neighborhood perfect graphs, Discrete math., 61, 93-101, (1986) · Zbl 0602.05053
[23] Lonc, Z.; Rival, I., Chains, antichains and fibres, J. combin. theory ser. A, 44, 207-228, (1987) · Zbl 0637.06001
[24] S.C. Sheu, The weighted clique transversal set problem on distance-hereditary graphs, Master Thesis, Department of Computer Science and Information Engineering, Chung Cheng University, Taiwan, 2001.
[25] Tuza, Zs., Covering all cliques of a graph, Discrete math., 86, 117-126, (1990) · Zbl 0744.05040
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.