J 2018

Optimal-size clique transversals in chordal graphs

COOPER, Jacob; Andrzej GRZESIK a Daniel KRÁĽ

Základní údaje

Originální název

Optimal-size clique transversals in chordal graphs

Autoři

COOPER, Jacob; Andrzej GRZESIK a Daniel KRÁĽ

Vydání

Journal of Graph Theory, Wiley, 2018, 0364-9024

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Impakt faktor

Impact factor: 0.883

DOI

UT WoS

000447648200007

EID Scopus

2-s2.0-85046352144

Klíčová slova anglicky

chordal graphs; clique transversals

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 13. 1. 2021 11:55, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.