Co-TT graphs and a characterization of split co-TT graphs

详细信息    查看全文

• 作者：Martin Charles Golumbic ; Nirit Lefel Weingarten ; Vincent Limouzy
• 关键词：Complement threshold tolerance graph ; Interval containment bigraph ; Interval graph ; Split graph
• 刊名：Discrete Applied Mathematics
• 出版年：11 March, 2014
• 年：2014
• 卷：165
• 期：Complete
• 页码：168-174
• 全文大小：518 K

文摘

In this paper, we present a new characterization of complement Threshold Tolerance graphs (co-TT for short) and find a recognition algorithm for the subclass of split co-TT graphs running in time. Currently, the best recognition algorithms for co-TT graphs and for split co-TT graphs run in time (Hammer and Simeone (1981) ; Monma et聽al. (1988) ).