Decomposition of P6-Free Chordal Bipartite Graphs
Summary :
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).
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.11 pp.1436-1439
- Publication Date
- 2023/11/01
- Publicized
- 2023/05/17
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2022EAL2103
- Type of Manuscript
- LETTER
- Category
- Graphs and Networks
Authors
Asahi TAKAOKA
Muroran Institute of Technology
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Asahi TAKAOKA, "Decomposition of P6-Free Chordal Bipartite Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E106-A, no. 11, pp. 1436-1439, November 2023, doi: 10.1587/transfun.2022EAL2103.
Abstract: 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).
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2022EAL2103/_p
Copy
@ARTICLE{e106-a_11_1436,
author={Asahi TAKAOKA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Decomposition of P6-Free Chordal Bipartite Graphs},
year={2023},
volume={E106-A},
number={11},
pages={1436-1439},
abstract={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).},
keywords={},
doi={10.1587/transfun.2022EAL2103},
ISSN={1745-1337},
month={November},}
Copy
TY - JOUR
TI - Decomposition of P6-Free Chordal Bipartite Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1436
EP - 1439
AU - Asahi TAKAOKA
PY - 2023
DO - 10.1587/transfun.2022EAL2103
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E106-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2023
AB - 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).
ER -
English
