Informace o publikaci
Optimal-size clique transversals in chordal graphs
| Autoři | |
|---|---|
| Rok publikování | 2018 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Journal of Graph Theory |
| Citace | |
| www | http://dx.doi.org/10.1002/jgt.22362 |
| Doi | http://dx.doi.org/10.1002/jgt.22362 |
| Klíčová slova | chordal graphs; clique transversals |
| Popis | 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. |