On covering all cliques of a chordal graph
type: Item
instance of: scholarly article
title: On covering all cliques of a chordal graph
zbMATH Open document ID: 0846.05050
DOI: 10.1016/0012-365X(94)00276-O
author: Carsten Flotow
author: Thomas Andreae
published in: Discrete Mathematics
publication date: 1996-03-26T00:00:00Z
review text: Let \(G\) be a graph without isolated vertices. A set \(T\subseteq V(G)\) is called a clique-transversal set if \(T\) has non-empty intersection with every maximal clique in \(G\). The clique-transversal number \(\tau_c(G)\) is the minimum cardinality of a clique-transversal set. Let \(\mathcal G\) denote the class of chordal graphs with the property that each edge is contained in a clique of order at least 4. The authors show that for each \(\varepsilon> 0\), there exists a graph \(G\in {\mathcal G}\) such that \(\tau_c(G)\geq ({2\over 7}- \varepsilon)\). They give some evidence to support their conjecture that \(\tau_c(G)\leq {2\over 7} |V(G)|\) for all \(G\in {\mathcal G}\).
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 858120
zbMATH Keywords: clique
zbMATH Keywords: clique-transversal number
zbMATH Keywords: clique-transversal set
zbMATH Keywords: chordal graphs
reviewed by: Brian Alspach
MaRDI profile type: Publication
cites work: Clique-transversal sets of line graphs and complements of line graphs
cites work: Fibres and ordered set coloring
cites work: Two-colouring all two-element maximal antichains
cites work: Covering the cliques of a graph with vertices
cites work: Chains, antichains, and fibres
cites work: A smallest-fibre-size to poset-size ratio approaching \({8 \over 15}\)
cites work: Covering all cliques of a graph
description: scientific article; zbMATH DE number 858120