Two remarks on circular arc graphs

被引:19
作者
Hell, P
Huang, J
机构
[1] SIMON FRASER UNIV,DEPT MATH & STAT,BURNABY,BC V5A 1S6,CANADA
[2] SIMON FRASER UNIV,SCH COMP SCI,BURNABY,BC V5A 1S6,CANADA
关键词
D O I
10.1007/BF01202237
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
In our first remark we observe a property of circular arcs which is similar to the Helly property and is helpful in describing all maximal cliques in circular are graphs (as well as allowing us to generalize a result of Tucker). Our main result is a new simple characterization of circular are graphs of clique covering number two. These graphs play a crucial role in recognition algorithms for circular are graphs, and have been characterized by several authors. Specifically, we show that a graph with clique covering number two is a circular are graph if and only if its edges can be coloured by two colours so that no induced four-cycle contains two opposite edges of the same colour. Our proof of the characterization depends on the 'lexicographic method' we have recently introduced. Both remarks could be useful in designing efficient algorithms for (maximum cliques in, respectively recognition of) circular are graphs.
引用
收藏
页码:65 / 72
页数:8
相关论文
共 18 条
[11]   O(M-CENTER-DOT-N) ALGORITHMS FOR THE RECOGNITION AND ISOMORPHISM PROBLEMS ON CIRCULAR-ARC GRAPHS [J].
HSU, WL .
SIAM JOURNAL ON COMPUTING, 1995, 24 (03) :411-439
[12]   AN O(N LOG N + M LOG LOG N) MAXIMUM WEIGHT CLIQUE ALGORITHM FOR CIRCULAR-ARC GRAPHS [J].
SHIH, WK ;
HSU, WL .
INFORMATION PROCESSING LETTERS, 1989, 31 (03) :129-134
[13]  
Spinard J., 1988, J COMB THEORY B, P300
[14]  
STOUFFERS KE, 1968, TRANSPORT RES, V2, P199
[15]   CHARACTERIZATION PROBLEMS FOR GRAPHS, PARTIALLY ORDERED SETS, LATTICES, AND FAMILIES OF SETS [J].
TROTTER, WT ;
MOORE, JI .
DISCRETE MATHEMATICS, 1976, 16 (04) :361-381
[16]   MATRIX CHARACTERIZATIONS OF CIRCULAR-ARC GRAPHS [J].
TUCKER, A .
PACIFIC JOURNAL OF MATHEMATICS, 1971, 39 (02) :535-&
[17]   EFFICIENT TEST FOR CIRCULAR-ARC GRAPHS [J].
TUCKER, A .
SIAM JOURNAL ON COMPUTING, 1980, 9 (01) :1-24
[18]   COLORING A FAMILY OF CIRCULAR ARCS [J].
TUCKER, A .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1975, 29 (03) :493-502