On the isomorphism of graphs with few P(4)s

被引：0
|
作者：
Babel, L [1 ]
Olariu, S [1 ]
机构：
[1] OLD DOMINION UNIV,DEPT COMP SCI,NORFOLK,VA 23529
来源：
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE | 1995年 / 1017卷
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We present new classes of graphs for which the isomorphism problem can be solved in polynomial time. These graphs are characterized by containing - in some local sense - only a small number of induced paths of length three. As it turns out, every such graph has a unique tree representation: the internal nodes correspond to three types of graph operations and the leaves are basic graphs with a simple structure. The paper extends and generalizes results on cographs, P-4-reducible graphs, and P-4-sparse graphs.
引用
收藏
页码：24 / 36
页数：13
相关论文
共 50 条
  • [1] Triangulating graphs with few P4's
    Babel, L
    DISCRETE APPLIED MATHEMATICS, 1998, 89 (1-3) : 45 - 57
  • [2] On the structure of graphs with few P4s
    Babel, L
    Olariu, S
    DISCRETE APPLIED MATHEMATICS, 1998, 84 (1-3) : 1 - 13
  • [3] HAMILTONICITY IN GRAPHS WITH FEW P-4S
    HOCHSTATTLER, W
    TINHOFER, G
    COMPUTING, 1995, 54 (03) : 213 - 225
  • [4] Hamiltonicity in graphs with few P4's
    University of Cologne, Cologne, D-50931, Germany
    不详
    Comput Vienna New York, 3 (213-225):
  • [5] The clique operator on graphs with few P4's
    de Mello, CP
    Morgana, A
    Liverani, M
    DISCRETE APPLIED MATHEMATICS, 2006, 154 (03) : 485 - 492
  • [6] Efficient algorithms for graphs with few P4'S
    Babel, L
    Kloks, T
    Kratochvíl, J
    Kratsch, D
    Müller, H
    Olariu, S
    DISCRETE MATHEMATICS, 2001, 235 (1-3) : 29 - 51
  • [7] On the Grundy number of graphs with few P4's
    Araujo, J.
    Linhares Sales, C.
    DISCRETE APPLIED MATHEMATICS, 2012, 160 (18) : 2514 - 2522
  • [8] Locally identifying coloring of graphs with few P4s
    Martins, Nicolas
    Sampaio, Rudini
    THEORETICAL COMPUTER SCIENCE, 2018, 707 : 69 - 76
  • [9] Restricted coloring problems on Graphs with few P4’s
    Cláudia Linhares-Sales
    Ana Karolinna Maia
    Nicolas Martins
    Rudini M. Sampaio
    Annals of Operations Research, 2014, 217 : 385 - 397
  • [10] Clique cycle transversals in graphs with few P4's
    Bravo, Raquel S. F.
    Klein, Sulamita
    Nogueira, Loana Tito
    Protti, Fabio
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2013, 15 (03): : 13 - 20
12345