Bounds on the clique-transversal number of regular graphs

DOI10.1007/s11425-007-0157-6zbMath1168.05046OpenAlexW1942892208MaRDI QIDQ943436

Erfang Shan, Cheng, T. C. Edwin, Li-ying Kang

Publication date: 9 September 2008

Published in: Science in China. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11425-007-0157-6

zbMATH Keywords

graphregular graphclique-transversal setclique-transversal numberclaw-free cubic graph

Mathematics Subject Classification ID

Hypergraphs (05C65) Structural characterization of families of graphs (05C75) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (9)

The clique-transversal set problem in \(\{\mathrm{claw},K_4\}\)-free planar graphs ⋮ Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs ⋮ Clique-transversal sets and clique-coloring in planar graphs ⋮ On the clique-transversal number in \({(\mathrm{claw},K_4)}\)-free 4-regular graphs ⋮ The clique-transversal set problem in claw-free graphs with degree at most 4 ⋮ The signed maximum-clique transversal number of regular graphs ⋮ Claw-free cubic graphs with clique-transversal number half of their order ⋮ Signed clique-transversal functions in graphs ⋮ The clique-transversal number of a \(\{K_{1, 3}, K_4 \}\)-free 4-regular graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum \(h\)-colourable subgraph problem in balanced graphs
• Clique-transversal sets of line graphs and complements of line graphs
• Chains, antichains, and fibres
• Covering all cliques of a graph
• Covering the cliques of a graph with vertices
• On the clique-transversal number of chordal graphs
• An upper bound for the transversal numbers of 4-uniform hypergraphs
• On clique-transversals and clique-independent sets
• Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
• Algorithmic aspects of clique-transversal and clique-independent sets
• The algorithmic complexity of the minus clique-transversal problem
• Distance-hereditary graphs are clique-perfect
• On balanced graphs
• Clique-Transversal Sets in Cubic Graphs
• Another note on cliques and independent sets
• Algorithmic Aspects of Neighborhood Numbers

This page was built for publication: Bounds on the clique-transversal number of regular graphs