zbMATH — the first resource for mathematics

Bounds on the clique-transversal number of regular graphs. (English) Zbl 1168.05046
Summary: A clique-transversal set \(D\) of a graph \(G\) is a set of vertices of \(G\) such that \(D\) meets all cliques of \(G\). The clique-transversal number, denoted \(\tau _c (G)\), is the minimum cardinality of a clique-transversal set in \(G\). In this paper we present the bounds on the clique-transversal number for regular graphs and characterize the extremal graphs achieving the lower bound. Also, we give the sharp bounds on the clique-transversal number for claw-free cubic graphs and we characterize the extremal graphs achieving the lower bound.

05C65 Hypergraphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C75 Structural characterization of families of graphs
PDF BibTeX Cite
Full Text: DOI
[1] Bondy J A, Murty U S R. Graph Theory with Applications. New York: Elsevier Publishing Co., Inc., 1986 · Zbl 1226.05083
[2] Berge C. Graphs and Hypergraphs. Amsterdam: North-Holland, 1973
[3] Andreae T, Schughart M, Tuza Z. Clique-transversal sets of line graphs and complements of line graphs. Discrete Math, 88: 11–20 (1991) · Zbl 0734.05077
[4] Haynes T W, Hedetniemi S T, Slater P J. Fundamentals of Domination in Graphs. New York: Marcel Dekker, 1998 · Zbl 0890.05002
[5] Erdos P, Gallai T, Tuza Z. Covering the cliques of a graph with vertices. Discrete Math, 108: 279–289 (1992) · Zbl 0766.05063
[6] Chang G J, Farber M, Tuza Z. Algorithmic aspects of neighbourhood numbers. SIAM J Discrete Math, 6: 24–29 (1993) · Zbl 0777.05085
[7] Guruswami V, Rangan C P. Algorithmic aspects of clique-transversal and clique-independent sets. Discrete Appl Math, 100: 183–202 (2000) · Zbl 0948.68135
[8] Chang M S, Chen Y H, Chang G J, et al. Algorithmic aspects of the generalized clique-transversal problem on chordal graphs. Discrete Appl Math, 66: 189–203 (1996) · Zbl 0854.68072
[9] Balachandhran V, Nagavamsi P, Ragan C P. Clique transversal and clique independence on comparability graphs. Inform Process Lett, 58: 181–184 (1996)
[10] Lee C M, Chang M S. Distance-hereditary graphs are clique-perfect. Discrete Appl Math, 154: 525–536 (2006) · Zbl 1110.68108
[11] Prisner E. Graphs with few cliques. In: Alavi Y, Schwenk A, eds. Graph Theory, Combinatorics and Applications. New York: Wiley, 1995, 945–956 · Zbl 0844.05062
[12] Tuza Z. Covering all cliques of a graph. Discrete Math, 86: 117–126 (1990) · Zbl 0744.05040
[13] Andreae T. On the clique-transversal number of chordal graphs. Discrete Math, 191: 3–11 (1998) · Zbl 0955.05058
[14] Bonomo F, Durán G, Groshaus M, et al. On clique-perfect and K-perfect graphs. Ars Combin, 80: 97–112 (2006) · Zbl 1224.05358
[15] Bonomo F, Durán G, Li M C, et al. On balanced graphs. Math Program Ser B, 105: 233–250 (2006) · Zbl 1080.05058
[16] Dahlhaus E, Mannuel P D, Miller M. Maximum h-colourable subgraph problem in balanced graphs. Inform Process Lett, 65: 301–303 (1998) · Zbl 1338.68098
[17] 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
[18] Galvin F. Another note on cliques and independent sets. J Graph Theory, 35: 173–175 (2000) · Zbl 0971.05088
[19] Lai F, Chang G J. An upper bound for the transversal numbers of 4-uniform hypergraphs. J Combin Theory Ser B, 50: 129–133 (1990) · Zbl 0739.05068
[20] Liang Z S, Shan E F, Cheng T C E. Clique-transversal sets in cubic graphs. In: Chen B, Paterson M, Zhang G, eds. ESCAPE 2007, LNCS Vol. 4614. Berlin: Springer-Verlag, 107–115 · Zbl 1176.05059
[21] Lonc Z, Rival I. Chains, antichains and fibers. J Combin Theory Ser A, 44: 207–228 (1987) · Zbl 0637.06001
[22] Xu G J, Shan E F, Kang L Y, et al. The algorithmic complexity of the minus clique-transversal problem. Appl Math Comput, 189: 1410–1418 (2007) · Zbl 1125.05076
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.