无爪图上团横贯数的界

Abstract

Abstract: A clique-transversal set $S$ of a graph $G=(V, E)$ is a subset of vertices of $G$ such that $S$ meets all cliques of $G$, where a clique is defined as a complete subgraph maximal under inclusion and having at least two vertices. The clique-transversal number, of $G$ denoted by $\tau_C(G)$, is the minimum cardinality of a clique-transversal set in $G$. In this paper we discuss the bound of clique-transversal numbers in several subclasses of claw-free graphs.

Key words: clique-transversal number, clique-transversal set, claw-free graph, bound

CLC Number:

O157.6

LIANG Zuosong,SHAN Erfang,GUAN Mei. The bound of clique-transversal numbers in claw-free graphs[J]. Operations Research Transactions, 2013, 17(2): 35-40.

References

Bondy J A, Murty U S R. Graph Theory [M]. Berlin: Springer, 2008.
King A D. Hitting all maximum cliques with a stable set using lopsided independent transversals [J]. Journal of Graph Theory, 2010, 67: 300-305.
Erd\H{o}s P, Gallai T, Tuza Z. Covering the cliques of a graph with vertices [J]. Discrete Math, 1992, 108: 279-289.
Chang G J, Farber M, Tuza Z. Algorithmic aspects of neighbourhood number [J]. SIAM J Discrete Math, 1993, 6: 24-29.
Guruswami V, Rangan C P. Algorithmic aspects of clique-transversal and clique-independent sets [J]. Discrete Appl Math, 2000, 100: 183-202.
Balachandhran V, Nagavamsi P,   Rangan C P. Clique transversal and clique independence on comparability graphs [J]. Information Processing Letters, 1996, 58: 181-184.
Lee C M, Chang M S. Distance-hereditary graphs are clique-perfect [J]. Discrete Appl Math, 2006, 154: 525-536.
Andreae T, Schughart M, Tuza Z. Clique-transversal sets of line graphs and complements of line graphs [J]. Discrete Math, 1991, 88: 11-20.
Bacs\'o G, Gravier S, Gy\'arf\'as A, et al. Coloring the maximal cliques of graphs [J]. SIAM J Discrete Math, 2004, 17: 361-376.
Bacs\'o G, Tuza Z. Clique-transversal sets and weak 2-colorings in graphs of small maximum degree [J]. Discrete Mathematics and Theoretical Computer Science, 2009, 11: 15-24.
Andreae T. On the clique-transversal number of chordal graphs [J]. Discrete Math, 1998, 191: 3-11.
Bonomo F, Chudnovsky M, Dur\'{a}n G. Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs [J]. Discrete Appl Math, 2008, 156: 1058-1082.
Dur\'{a}n G, Lin M C,   Szwarcfiter J L. On clique-transversals and clique-independent sets [J]. Annals of Operations Research, 2002, 116: 71-77.
Lakshmanan S A, Vijayakumar A. The $\langle t \rangle$-property of some classes of graphs [J]. Discrete Math, 2008, 309: 259-263.
Liang Z S, Shan E F. Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs [J]. Information Processing Letters, 2011, 111: 1104-1107.
Shan E F, Cheng T C E, Kang L Y. Bounds on the clique-transversal number of regular graphs [J]. Science in China A: Mathematics, 2008, 51: 851-863.
Tuza Z. Covering all cliques of a graph [J]. Discrete Math., 1990, 86: 117-126.
Chudnovsky M, Seymour P.   Claw-free graphs IV. Decomposition theorem [J]. J. Combin. Theory Ser. B, 2008, 98: 839-938.
Chudnovsky M, Seymour P.   Claw-free graphs III. Circular interval graphs [J]. J. Combin. Theory Ser. B, 2008, 98: 812-834.
Cerioli M R, Korenchendler A L. Clique-coloring circular-arc graphs [J]. Electronic Notes in Discrete Mathematics, 2009, 35: 287-292.

[1]	REN Yequan, BAI Yanqin, LI Qian, YU Changjun, ZHANG Liansheng. A second-order cone programming algorithm for pooling problem [J]. Operations Research Transactions, 2020, 24(2): 61-72.
[2]	LI Wenhua, ZHAI Weina, CHAI Xing, GAO Chao. On-line bounded-batching scheduling of unit-length jobs with two families [J]. Operations Research Transactions, 2019, 23(4): 105-110.
[3]	TAO Yanliang, HUANG Qiongxiang, CHEN Lin. Contraction graph method for the interval edge-colorings of graphs [J]. Operations Research Transactions, 2019, 23(2): 31-43.
[4]	CAI Shuang, YANG Ke, LIU Ke. Model and algorithms of the distributed permutation flow shop scheduling problem with machine eligibility constraints [J]. Operations Research Transactions, 2018, 22(4): 17-30.
[5]	GAO Leifu, ZHANG Yahong. A penalized FB function for symmetric cone complementarity problems [J]. Operations Research Transactions, 2018, 22(3): 125-131.
[6]	HE Simai, JIN Yujia, WANG Hua, GE Dongdong. A survey on online learning methods: Thompson sampling and others [J]. Operations Research Transactions, 2017, 21(4): 84-102.
[7]	LI Shan, SHAN Erfang, ZHANG Lin. A note on total domination in 5-regular graphs [J]. Operations Research Transactions, 2017, 21(1): 125-128.
[8]	YANG Guanghui, YANG Hui, XIANG Shuwen. Stability of solutions to parametric optimization problems under bounded rationality [J]. Operations Research Transactions, 2016, 20(4): 1-10.
[9]	WANG Chun, QIU Xiaoling, WANG Nengfa, CHEN Pinbo. Stability to bounded rationality for nonconvexity [J]. Operations Research Transactions, 2016, 20(3): 107-120.
[10]	ZHENG Wei, WANG Ligong. The Hamilton-connectivity with the degree sum of non-adjacent subgraphs P_ 4 and K_1 in claw-free graphs [J]. Operations Research Transactions, 2016, 20(1): 112-117.
[11]	TANG Guochun, LIU Xiaohui. Applications of operations research in automotive parts inbound logistics [J]. Operations Research Transactions, 2015, 19(3): 123-130.
[12]	LIU Yuanwen, OU Yigui. A hybrid method for a system of nonlinear equations with bound constraints [J]. Operations Research Transactions, 2015, 19(1): 45-56.
[13]	ZHANG Huizhen, WEI Xin, MA Liang. The bounded simplex method to solve the 0-1 linear integer programming problem [J]. Operations Research Transactions, 2014, 18(3): 71-78.
[14]	FENG Zengzhe, ZHANG Xixue, LIU Jianbo$, FANG Liang. A new wide neighborhood infeasible interior-point algorithm for semidefinite programming [J]. Operations Research Transactions, 2014, 18(2): 49-58.
[15]	LI Gaidi, WANG Zhen, WU Yulin. Bicriteria approximation algorithms for the lower-bounded facility location problem with penalties and soft-capacity [J]. Operations Research Transactions, 2013, 17(1): 117-126.

The bound of clique-transversal numbers in claw-free graphs

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments