|
| | | |
Black-and-White Threshold Graphs
Hung, L.-J., Kloks, T. and Villaamil, F. S.
Let k be a natural number. We introduce k-threshold graphs. We show that there exists an O(n3) algorithm for the recognition of k-threshold graphs for each natural number k. k-Threshold graphs are characterized by a finite collection of forbidden induced subgraphs. For the case k = 2 we characterize the partitioned 2- threshold graphs by forbidden induced subgraphs. We introduce restricted, and special 2-threshold graphs. We characterize both classes by forbidden induced subgraphs. The restricted 2-threshold graphs coincide with the switching class of threshold graphs. This provides a decomposition theorem for the switching class of threshold graphs. |
Cite as: Hung, L.-J., Kloks, T. and Villaamil, F. S. (2011). Black-and-White Threshold Graphs. In Proc. Computing: The Australasian Theory Symposium (CATS 2011) Perth, Australia. CRPIT, 119. Alex Potanin and Taso Viglas Eds., ACS. 121-130 |
(from crpit.com)
(local if available)
|
|