COOPER, Jacob, Andrzej GRZESIK and Daniel KRÁĽ. Optimal-size clique transversals in chordal graphs. Journal of Graph Theory. Wiley, 2018, vol. 89, No 4, p. 479-493. ISSN 0364-9024. Available from: https://dx.doi.org/10.1002/jgt.22362.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Optimal-size clique transversals in chordal graphs
Authors COOPER, Jacob, Andrzej GRZESIK and Daniel KRÁĽ.
Edition Journal of Graph Theory, Wiley, 2018, 0364-9024.
Other information
Original language English
Type of outcome Article in a journal
Field of Study 10101 Pure mathematics
Country of publisher United States of America
Confidentiality degree is not subject to a state or trade secret
WWW URL
Impact factor Impact factor: 0.883
Doi http://dx.doi.org/10.1002/jgt.22362
UT WoS 000447648200007
Keywords in English chordal graphs; clique transversals
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 13/1/2021 11:55.
Abstract
The following question was raised by Tuza in 1990 and Erdős 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 nontrivial 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.
PrintDisplayed: 28/9/2024 13:43