A local characterization for perfect plane near-triangulations

被引：1
|
作者：
Salam, Sameera M. [1 ]
Babu, Jasine [2 ]
Krishnan, K. Murali [1 ]
机构：
[1] Natl Inst Technol Calicut, Dept Comp Sci & Engn, Calicut 673601, Kerala, India
[2] Indian Inst Technol, Dept Comp Sci & Engn, Palakkad 678557, Kerala, India
来源：
THEORETICAL COMPUTER SCIENCE | 2020年 / 840卷
关键词：
Plane near-triangulated graphs; Plane triangulated graphs; Perfect graphs;
D O I：
10.1016/j.tcs.2020.06.031
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We derive a local criterion for a plane near-triangulated graph to be perfect. It is shown that a plane near-triangulated graph is perfect if and only if it does not contain either a vertex, an edge or a triangle, the neighbourhood of which has an odd hole as its boundary. The characterization leads to an O(n(2)) algorithm for checking perfectness of plane near-triangulations. (C) 2020 Elsevier B.V. All rights reserved.
引用
收藏
页码：45 / 58
页数：14
相关论文
共 50 条
  • [21] Graphs of triangulations and perfect matchings
    Houle, ME
    Hurtado, F
    Noy, M
    Rivera-Campo, E
    GRAPHS AND COMBINATORICS, 2005, 21 (03) : 325 - 331
  • [22] Graphs of Triangulations and Perfect Matchings
    M.E. Houle
    F. Hurtado
    M. Noy
    E. Rivera-Campo
    Graphs and Combinatorics, 2005, 21 : 325 - 331
  • [23] CONNECTIVITY OF PLANE TRIANGULATIONS
    LAUMOND, JP
    INFORMATION PROCESSING LETTERS, 1990, 34 (02) : 87 - 96
  • [24] RANDOM TRIANGULATIONS OF THE PLANE
    RICHMOND, LB
    WORMALD, NC
    EUROPEAN JOURNAL OF COMBINATORICS, 1988, 9 (01) : 61 - 71
  • [25] Dominating plane triangulations
    Plummer, Michael D.
    Ye, Dong
    Zha, Xiaoya
    DISCRETE APPLIED MATHEMATICS, 2016, 211 : 175 - 182
  • [26] Dominating plane triangulations
    Plummer, Michael D.
    Ye, Dong
    Zha, Xiaoya
    Discrete Applied Mathematics, 2016, 211 : 175 - 182
  • [27] Hamilton cycles in plane triangulations
    Jackson, B
    Yu, XX
    JOURNAL OF GRAPH THEORY, 2002, 41 (02) : 138 - 150
  • [28] On light cycles in plane triangulations
    Discrete Math, (453-467):
  • [29] The domination number of plane triangulations
    Spacapan, Simon
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2020, 143 : 42 - 64
  • [30] Dominating sets in plane triangulations
    King, Erika L. C.
    Pelsmajer, Michael J.
    DISCRETE MATHEMATICS, 2010, 310 (17-18) : 2221 - 2230
12345