@inproceedings{f05b738bcd7442979728677d53b83820,
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 show that, for a reducible graph \$G\$, the minimum number of required rounds is \$O(\textbackslash{}sqrt\{\textbackslash{}alpha\}\$, where \$\textbackslash{}alpha\$ is the independence number of \$G\$. This upper bound is tight and the result implies the square-root conjecture which was first posed in MFCS 2004. We also show that for reducible \$K\_\{1,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.",
author = "Broersma, \{Haitze J.\} and Matthew Johnson and Dani{\"e}l Paulusma",
year = "2007",
month = jul,
doi = "10.1007/978-3-540-72951-8\_26",
language = "English",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
number = "1",
pages = "328--340",
editor = "Giuseppe Prencipe and Shmuel Zaks",
booktitle = "SIROCCO 2007: 14th International Colloquium on Structural Information and Communication Complexity",
address = "Germany",
note = "14th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2007 ; Conference date: 05-06-2007 Through 08-06-2007",
}