A note on the recognition of bisplit graphs |
| |
| Authors: | Atif Abueida |
| |
| Affiliation: | a Department of Mathematics, The University of Dayton, Dayton, OH 45469, USA
b Computer Science Department, The University of Dayton, Dayton, OH 45469, USA |
| |
| Abstract: | We show that bisplit graphs can be recognized in O(n2) time. The previous best bound of O(mn) for the problem appeared in a recently published article [A. Brandstädt, P.L. Hammer, V.B. Le, V.V. Lozin, Bisplit graphs, Discrete Math. 299 (2005) 11-32] in this journal. |
| |
| Keywords: | Bisplit graphs 3-colorable graphs Recognition algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
