ON CHORDAL PROPER CIRCULAR-ARC GRAPHS

被引：10

作者：

BANGJENSEN, J

HELL, P

机构：

[1] ODENSE UNIV,DEPT MATH & COMP SCI,DK-5230 ODENSE,DENMARK

[2] SIMON FRASER UNIV,SCH COMP SCI,BURNABY V5A 1S6,BC,CANADA

来源：

DISCRETE MATHEMATICS | 1994年 / 128卷 / 1-3期

关键词：

D O I：

10.1016/0012-365X(94)90130-9

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Wegner proved that a chordal graph is a proper interval graph if and only if it is claw-free, net-free and tent-free. We observe that in fact the characterization can be refined to say that a chordal graph is a proper interval graph if and only if it is claw-free, net-free and not a multiple of the tent. This observation implies that a chordal graph is a proper circular arc graph if and only if it is claw-free and net-free. A further implication of this result is that a chordal graph can be oriented as a local tournament - an oriented graph in which the predecessors as well as the successors of any vertex induce a tournament - if and only if it is claw-free and net-free.

引用

页码：395 / 398

页数：4

共 6 条

[1] LOCALLY SEMICOMPLETE DIGRAPHS - A GENERALIZATION OF TOURNAMENTS [J].