Optimal‐size clique transversals in chordal graphs

DOI10.1002/JGT.22362zbMATH Open1402.05213arXiv1601.05305OpenAlexW2964047879WikidataQ129902463 ScholiaQ129902463MaRDI QIDQ4646950FDOQ4646950

Authors: Jacob W. Cooper, A. Grzesik, Daniel Král' 

Publication date: 3 January 2019

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: The following question was raised by Tuza in 1990 and Erdos et al. in 1992: if every edge of an n-vertex chordal graph G is contained in a clique of size at least four, does G have a clique transversal, i.e., a set of vertices meeting all non-trivial maximal cliques, of size at most n/4? We prove that every such graph G has a clique transversal of size at most 2(n-1)/7 if n>=5, which is the best possible bound.

Full work available at URL: https://arxiv.org/abs/1601.05305

Recommendations

• On the clique-transversal number of chordal graphs
• Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
• Approximability of clique transversal in perfect graphs
• Approximation algorithms for clique transversals on some graph classes
• scientific article; zbMATH DE number 2044919
• A generalization of chordal graphs and the maximum clique problem
• Variations of maximum-clique transversal sets on graphs
• scientific article; zbMATH DE number 4134082
• Algorithms for finding clique-transversals of graphs
• Transversals of longest cycles in chordal and bounded tree-width graphs

zbMATH Keywords

chordal graphsclique transversals

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Transversal (matching) theory (05D15)

Cited In (6)

• Sizes and transmissions of digraphs with a given clique number
• Clique Partitions of Chordal Graphs
• On the clique-transversal number of chordal graphs
• Transversals of longest cycles in chordal and bounded tree-width graphs
• Upper Clique Transversals in Graphs
• LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs

This page was built for publication: Optimal‐size clique transversals in chordal graphs

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