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

DOI10.1016/J.IPL.2014.10.008zbMATH Open1304.05138OpenAlexW1975220870MaRDI QIDQ477680FDOQ477680

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

Recommendations

• The clique-transversal set problem in \(\{\mathrm{claw},K_4\}\)-free planar graphs
• The bound of clique-transversal numbers in claw-free graphs
• Clique-transversal sets in 4-regular claw-free graphs
• Clique-transversal sets and weak 2-colorings in graphs of small maximum degree
• On the clique-transversal number in \({(\mathrm{claw},K_4)}\)-free 4-regular graphs

zbMATH Keywords

graph algorithmsclaw-free graphcliquepolynomial-time algorithmclique-transversal set problem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• Title not available (Why is that?)
• Clique-transversal sets in 4-regular claw-free graphs
• Analyzing lattice networks through substructures
• Vertex-based and edge-based centroids of graphs
• The clique-transversal set problem in \(\{\mathrm{claw},K_4\}\)-free planar graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477680)