@article { ,
title = {Upper bounds and algorithms for parallel knock-out numbers},
abstract = {We study parallel knock-out schemes for graphs. These schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the graph. We resolve the square-root conjecture, first posed at MFCS 2004, by showing that for a reducible graph G, the minimum number of required rounds is View the MathML source; in fact, our result is stronger than the conjecture as we show that the minimum number of required rounds is View the MathML source, where α is the independence number of G. This upper bound is tight. We also show that for reducible K1,p-free graphs at most p−1 rounds are required. It is already known that the problem of whether a given graph is reducible is NP-complete. For claw-free graphs, however, we show that this problem can be solved in polynomial time. We also pinpoint a relationship with (locally bijective) graph homomorphisms.},
doi = {10.1016/j.tcs.2008.03.024},
issn = {0304-3975},
issue = {14},
journal = {Theoretical Computer Science},
note = {EPrint Processing Status: Full text deposited in DRO},
pages = {1319-1327},
publicationstatus = {Published},
publisher = {Elsevier},
volume = {410},
keyword = {Algorithms and Complexity in Durham (ACiD), Parallel knock-out schemes, Claw-free graphs, Computational complexity.},
year = {2009},
author = {Broersma, H.J. and Johnson, M. and Paulusma, D.}
}