Balanced online Ramsey games in random graphs.
Let denote a path with edges and denote the -fold complete bipartite graph with both parts of size . In this paper, we obtain the necessary and sufficient conditions for to have a balanced -decomposition. We also obtain the directed version of this result.
Suppose a graph G = (V,E) with edge weights w(e) and edges partitioned into disjoint categories S₁,...,Sₚ is given. We consider optimization problems on G defined by a family of feasible sets (G) and the following objective function: For an arbitrary number of categories we show that the L₅-perfect matching, L₅-a-b path, L₅-spanning tree problems and L₅-Hamilton cycle (on a Halin graph) problem are NP-complete. We also summarize polynomiality results concerning above objective functions for arbitrary...
We prove that the multiplicity of a simple module as a composition factor in a composition series for a primitive band module over a domestic string algebra is at most two.