During the last decades, numerous studies have been undertaken on the classes of net-free graphs, claw-free graphs, and the relationship between them. The notion of weakly decomposition (a partition of the set of vertices in three classes A, B, C such that A induces a connected graph and C is totally adjacent to B and totally non-adjacent to A) and the study of its properties allow us to obtain several important results such as: characterization of cographs, {P4,C4}-free and paw-free graphs. In this article, we give a characterization of net-free graphs, a characterization of claw-free graphs, using weakly decomposition. Also, we give a recognition algorithm for net-free graphs, an algorithm for determining a maximum matching in claw-free graphs, comparable with existing algorithms in terms of complexity, but using weakly decomposition.
net-free graphs, claw-free graphs, asteroidal triple-free graphs, weakly decomposition, recognition algorithm, maximum matching in graphs.
Mihai Talmaciu, Victor Lepin, "Algorithms for the Recognition of Net-free Graphs and for Computing Maximum Cardinality Matchings in Claw-free Graphs", Studies in Informatics and Control, ISSN 1220-1766, vol. 23(2), pp. 183-188, 2014. https://doi.org/10.24846/v23i2y201406
All articles published by Studies in Informatics and Control (SIC) are published in accordance with the terms and conditions of the Creative Commons Attribution License (CC BY-NC-SA 4.0).