Other formats:
BibTeX
LaTeX
RIS
@article{1554844, author = {Cooper, Jacob and Grzesik, Andrzej and Kráľ, Daniel}, article_number = {4}, doi = {http://dx.doi.org/10.1002/jgt.22362}, keywords = {chordal graphs; clique transversals}, language = {eng}, issn = {0364-9024}, journal = {Journal of Graph Theory}, title = {Optimal-size clique transversals in chordal graphs}, url = {http://dx.doi.org/10.1002/jgt.22362}, volume = {89}, year = {2018} }
TY - JOUR ID - 1554844 AU - Cooper, Jacob - Grzesik, Andrzej - Kráľ, Daniel PY - 2018 TI - Optimal-size clique transversals in chordal graphs JF - Journal of Graph Theory VL - 89 IS - 4 SP - 479-493 EP - 479-493 PB - Wiley SN - 03649024 KW - chordal graphs KW - clique transversals UR - http://dx.doi.org/10.1002/jgt.22362 L2 - http://dx.doi.org/10.1002/jgt.22362 N2 - 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. ER -
COOPER, Jacob, Andrzej GRZESIK and Daniel KRÁĽ. Optimal-size clique transversals in chordal graphs. \textit{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.
|