On bipartite graphs with weak density of some subgraphs

被引：1
作者：
Fouquet, Jean-Luc [1 ]
Vanherpe, Jean-Marie [1 ]
机构：
[1] LIFO, F-45067 Orleans, France
来源：
DISCRETE MATHEMATICS | 2007年 / 307卷 / 11-12期
关键词：
sparse graphs; bipartite graphs decomposition;
D O I：
10.1016/j.disc.2005.11.089
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
P-4-sparse graphs (defined by Hoang) and P-4-reducible graphs (defined by Jamison and Olariu) are graphs with weak density of P-4's. Weak-bisplit graphs are bipartite graphs which show some analogies with cographs (i.e. P-4-free graphs) and are characterized with two forbidden configurations. We describe here bipartite graphs with weak density of those configurations. Structural properties and recognition algorithms are given. (c) 2006 Elsevier B.V. All rights reserved.
引用
收藏
页码：1516 / 1524
页数：9
相关论文
共 17 条
  • [1] Bondy J.A., 1979, Graph Theory with Applications
  • [2] CLASSES OF BIPARTITE GRAPHS RELATED TO CHORDAL GRAPHS
    BRANDSTADT, A
    [J]. DISCRETE APPLIED MATHEMATICS, 1991, 32 (01) : 51 - 60
  • [3] COMPLEMENT REDUCIBLE GRAPHS
    CORNEIL, DG
    LERCHS, H
    BURLINGHAM, LS
    [J]. DISCRETE APPLIED MATHEMATICS, 1981, 3 (03) : 163 - 174
  • [4] A LINEAR RECOGNITION ALGORITHM FOR COGRAPHS
    CORNEIL, DG
    PERL, Y
    STEWART, LK
    [J]. SIAM JOURNAL ON COMPUTING, 1985, 14 (04) : 926 - 934
  • [5] Matroids arisen from matrogenic graphs
    Ding, GL
    Hammer, PL
    [J]. DISCRETE MATHEMATICS, 1997, 165 : 211 - 217
  • [6] Fouquet J.-L., 1999, International Journal of Foundations of Computer Science, V10, P513, DOI 10.1142/S0129054199000368
  • [7] FROST HB, 1990, ARS COMBINATORIA, V29, P283
  • [8] Garey MR, 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
  • [9] Giakoumakis V., 2003, International Journal of Foundations of Computer Science, V14, P107, DOI 10.1142/S0129054103001625
  • [10] Bi-complement reducible graphs
    Giakoumakis, V
    Vanherpe, JM
    [J]. ADVANCES IN APPLIED MATHEMATICS, 1997, 18 (04) : 389 - 402
12