Structure of Research Survey

Zsolt Tuza

1. Vertex colorings of graphs (a) Colorings and orientations

(b) Chromatic sum

(c) Precoloring extension

(d) List colorings

(e) Maximal independent sets

2. Edge colorings (a) Strong matchings

(b) Properly colored subgraphs

3. Coverings and decompositions of graphs (a) Dominating sets

(b) Neighborhood coverings

(c) Clique and bi-clique coverings

(d) Decompositions into perfect subgraphs

(e) Clique transversals

4. Optimization problems (a) Maximum cuts

(b) Multiprocessor scheduling

5. Intercommunication networks (a) Menger path systems

(b) Optimal routings

6. Further problems on graphs (a) Ramsey theory for local k-colorings (b) Edge labelings

(c) Packings and coverings of triangles (d) Graph entropy 7. Hypergraphs and design theory (a) The set-pair method

(b) The Helly property

(c) Intersection-critical and transversalcritical hypergraphs

(d) Multipartite hypergraphs

(e) Saturated graphs and hypergraphs (f) Blocking sets in Steiner systems

8. Theoretical computer science (a) Satisfiability

(b) Formal languages

(c) Parallel rewriting

9. Applications of combinatorial methods in algebra

(a) Polynomial identities over matrix rings

(b) Representations of relation algebras (c) Axiomatizability of polyadic algebras

10. Applications in other fields

(a) Process control in chemical engineering

(b) Developmental biology: Cell division and differentiation

(c) Combinatorial problems in geometry