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 条

[31] CONNECTED DOMINATION IN PLANE TRIANGULATIONS
arXiv, 1600,
[32] On light cycles in plane triangulations
Jendrol, S
Madaras, T
Soták, R
Tuza, Z
DISCRETE MATHEMATICS, 1999, 197 (1-3) : 453 - 467
[33] Plane triangulations in product graphs
Paulraja, P
Varadarajan, N
ARS COMBINATORIA, 2004, 71 : 225 - 237
[34] GENERATING THE TRIANGULATIONS OF THE PROJECTIVE PLANE
BARNETTE, D
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1982, 33 (03) : 222 - 230
[35] Geometric transformations in plane triangulations
Kawarabayashi, K
Nakamoto, A
Oda, Y
Watanabe, M
DISCRETE AND COMPUTATIONAL GEOMETRY, 2001, 2098 : 217 - 221
[36] On triangulations of the plane by pencils of conics
Lazareva, V. B.
Shelekhov, A. M.
SBORNIK MATHEMATICS, 2007, 198 (11-12) : 1637 - 1663
[37] Total domination in plane triangulations
Claverol, Merce
Garcia, Alfredo
Hernandez, Gregorio
Hernando, Carmen
Maureso, Montserrat
Mora, Merce
Tejel, Javier
DISCRETE MATHEMATICS, 2021, 344 (01)
[38] Describing faces in plane triangulations
Borodin, O. V.
Ivanova, A. O.
Kostochka, A. V.
DISCRETE MATHEMATICS, 2014, 319 : 47 - 61
[39] Rigidity of the Delaunay triangulations of the plane
Dai, Song
Wu, Tianqi
ADVANCES IN MATHEMATICS, 2024, 456
[40] On rainbow matchings in plane triangulations
Jendrol, Stanislav
DISCRETE MATHEMATICS, 2019, 342 (12)

← 1 2 3 4 5 →