The Computational Complexity of the Parallel Knock-Out Problem
We consider computational complexity questions related to parallel knock-out schemes for graphs. In such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its neighbours. We show that the problem of whether, for a given graph, such a scheme can be found that eliminates every vertex is NP-complete. Moreover, we show that, for all fixed positive integers k ≥ 2, the problem of whether a given graph admits a scheme in which all vertices are eliminated in at most k rounds is NP-complete. For graphs with bounded tree-width, however, both of these problems are shown to be solvable in polynomial time.

title: Amalgamations of connected k-factorizations
abstract: In this paper, necessary and sufficient conditions are found for a graph with exactly one amalgamated vertex to be the amalgamation of a k-factorization of Kkn+1 in which each k factor is connected. From this result, necessary and sufficient conditions for a given edge-coloured Kt to be embedded in a connected k-factorization of Kkn+1 are deduced.

title: Path factors and parallel knock-out schemes of almost claw-free graphs
abstract: An H"1,{H"2}-factor of a graph G is a spanning subgraph of G with exactly one component isomorphic to the graph H"1 and all other components (if there are any) isomorphic to the graph H"2. We completely characterise the class of connected almost claw-free graphs that have a P"7,{P"2}-factor, where P"7 and P"2 denote the paths on seven and two vertices, respectively. We apply this result to parallel knock-out schemes for almost claw-free graphs. These schemes proceed in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is reducible if such a scheme eliminates every vertex in the graph. Using our characterisation, we are able to classify all reducible almost claw-free graphs, and we can show that every reducible almost claw-free graph is reducible in at most two rounds. This leads to a quadratic time algorithm for determining if an almost claw-free graph is reducible (which is a generalisation and improvement upon the previous strongest result that showed that there was a O(n^5^.^3^7^6) time algorithm for claw-free graphs on n vertices).

title: Amalgamations of factorizations of complete equipartite graphs
abstract: Let t be a positive integer, and let L=(l"1,...,l"t) and K=(k"1,...,k"t) be collections of nonnegative integers. A graph has a (t,K,L) factorization if it can be represented as the edge-disjoint union of factors F"1,...,F"t where, for 1=

title: Obtaining Online Ecological Colourings by Generalizing First-Fit
abstract: A colouring of a graph is ecological if every pair of vertices that have the same set of colours in their neighbourhood are coloured alike. We consider the following problem: if a graph G and an ecological colouring c of G are given, can further vertices added to G, one at a time, be coloured using colours from some finite set C so that at each stage the current graph is ecologically coloured? If the answer is yes, then we say that the pair (G,c) is ecologically online extendible. By generalizing the well-known First-Fit algorithm, we are able to characterize when (G,c) is ecologically online extendible. For the case where c is a colouring of G in which each vertex is coloured distinctly, we give a simple characterization of when (G,c) is ecologically online extendible using only the colours of c, and we also show that (G,c) is always online extendible if we permit ourselves to use one extra colour. We also study (off-line) ecological H-colourings where the colouring must satisfy further restrictions imposed by some fixed pattern graph H. We characterize the computational complexity of this problem. This solves an open question posed by Crescenzi et al.

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(√α), where α 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 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.

title: Characterization of graphs with hall number 2
abstract: Hall’s condition is a simple condition that a graph G and list assignment L must satisfy if G has a proper L-colouring. The Hall number of G is the smallest integer m such that whenever each list has size m and Hall’s condition is satisfied a proper L-colouring exists. Hilton and P.D. Johnson introduced the parameter and showed that a graph has Hall number 1 if and only if every block is a clique. In this paper we characterize graphs with Hall number 2. ∗Current address: London School of Economics, Houghton Street, London WC2A 2AE, U.K.

title: Defining sets for Latin squares given that they are based on groups
abstract: We investigate defining sets for Latin squares where we are given that the Latin square is the Cayley table for some group. Our main result is that the proportion of entries in a smallest defining set approaches zero as the order of the group increases without bound.