The clique-transversal set problem in claw-free graphs with degree at most 4

DOI10.1016/j.ipl.2014.10.008zbMath1304.05138OpenAlexW1975220870MaRDI QIDQ477680

Erfang Shan, Zuosong Liang

Publication date: 9 December 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2014.10.008

zbMATH Keywords

claw-free graphpolynomial-time algorithmgraph algorithmscliqueclique-transversal set problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (3)

The clique-transversal set problem in \(\{\mathrm{claw},K_4\}\)-free planar graphs ⋮ Analyzing lattice networks through substructures ⋮ Vertex-based and edge-based centroids of graphs

Cites Work

• Unnamed Item
• Clique-transversal sets of line graphs and complements of line graphs
• Algorithms for finding clique-transversals of graphs
• Bounds on the clique-transversal number of regular graphs
• Covering all cliques of a graph
• Covering the cliques of a graph with vertices
• On clique-transversals and clique-independent sets
• On covering all cliques of a chordal graph
• Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
• Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs
• Algorithmic aspects of clique-transversal and clique-independent sets
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Distance-hereditary graphs are clique-perfect
• On balanced graphs
• Algorithmic Aspects of Neighborhood Numbers

This page was built for publication: The clique-transversal set problem in claw-free graphs with degree at most 4