平面图上的团横贯数与独立数

摘要

设G为简单图,若G的点子集S与图中的每个团都有非空的交,则称S是图G的一个团横贯集,这里G的团是指图中的极大完全子图且至少包含两个点.图G的最小团横贯集所含点的数目称为G的团横贯数,记作τC(G).如果G的每条边至少包含在一个t阶完全子图中且τC(G)≤|V(G)|/t,则称G具有〈t〉一性质.提出了平面图分离4-团的概念.首先证明了最大度不超过5的平面图具有〈t〉-性质.其次,对任意平面图G,若它不含分离4-团且每条边都包含在一个4-团之中,得到了它的横贯数的上界和独立数的可达下界.