Diamond-free circle graphs are Helly circle

被引：6
作者：
Daligault, Jean [1 ]
Goncalves, Daniel [1 ]
Rao, Michael [2 ]
机构：
[1] Univ Montpellier 2, LIRMM, F-34392 Montpellier, France
[2] Univ Bordeaux 1, LABRI, F-33405 Talence, France
来源：
DISCRETE MATHEMATICS | 2010年 / 310卷 / 04期
关键词：
Circle graph; Helly property; OBSTRUCTIONS; RECOGNITION;
D O I：
10.1016/j.disc.2009.09.022
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
The diamond is the graph obtained from K(4) by deleting an edge. Circle graphs are the intersection graphs of chords in a circle. Such a circle model has the Helly property if every three pairwise intersecting chords intersect in a single point, and a graph is Helly circle if it has a circle model with the Helly property. We show that the Helly circle graphs are the diamond-free circle graphs, as conjectured by Duran. This characterization gives an efficient recognition algorithm for Helly circle graphs. (C) 2009 Elsevier B.V. All rights reserved.
引用
收藏
页码：845 / 849
页数：5
相关论文
共 15 条
  • [1] BARIONUEVO JM, 2004, ELECT NOTES DISCRETE, V18, P31
  • [2] CIRCLE GRAPH OBSTRUCTIONS
    BOUCHET, A
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 60 (01) : 107 - 144
  • [3] REDUCING PRIME GRAPHS AND RECOGNIZING CIRCLE GRAPHS
    BOUCHET, A
    [J]. COMBINATORICA, 1987, 7 (03) : 243 - 254
  • [4] Courcelle B., 2008, J APPL LOGIC, V6, P416, DOI DOI 10.1016/J.JAL.2007.05.001
  • [5] DECOMPOSITION OF DIRECTED-GRAPHS
    CUNNINGHAM, WH
    [J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1982, 3 (02): : 214 - 228
  • [6] de Fraysseix H., 1984, European J. Combin., V5, P223
  • [7] Duran G., 2000, THESIS U BUENOS AIRE
  • [8] Durán Guillermo, 2003, Pesqui. Oper., V23, P221, DOI 10.1590/S0101-74382003000100016
  • [9] GABOR P, 1985, P 26 IEEE ANN S
  • [10] Circle Graph Obstructions Under Pivoting
    Geelen, Jim
    Oum, Sang-il
    [J]. JOURNAL OF GRAPH THEORY, 2009, 61 (01) : 1 - 11
12