The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] modular decomposition(1hit)

1-1hit
  • Decomposition of P6-Free Chordal Bipartite Graphs

    Asahi TAKAOKA  

     
    LETTER-Graphs and Networks

      Pubricized:
    2023/05/17
      Vol:
    E106-A No:11
      Page(s):
    1436-1439

    Canonical decomposition for bipartite graphs, which was introduced by Fouquet, Giakoumakis, and Vanherpe (1999), is a decomposition scheme for bipartite graphs associated with modular decomposition. Weak-bisplit graphs are bipartite graphs totally decomposable (i.e., reducible to single vertices) by canonical decomposition. Canonical decomposition comprises series, parallel, and K+S decomposition. This paper studies a decomposition scheme comprising only parallel and K+S decomposition. We show that bipartite graphs totally decomposable by this decomposition are precisely P6-free chordal bipartite graphs. This characterization indicates that P6-free chordal bipartite graphs can be recognized in linear time using the recognition algorithm for weak-bisplit graphs presented by Giakoumakis and Vanherpe (2003).