Connectivity and Colorings of Graphs.

摘要

The research performed with the support of this grant has focused on the graph theoretical issues of colorings of various forms, connectivity issues of a traditional form and as applied to network vulnerability, and some work on extremal and worst-case scenarios. Coloring problems considered included the development of the method of amalgamations, which takes an 'outline' version of a structure of interest and shows how to develop it into the completed version. This produced, for example, a constructive proof that there exist hamilton decompositions of complete multipartite graphs that are fair in the sense that the edges between pairs of parts are shared out evenly among the hamilton cycles. The method was also improved to the point where notable results concerning connected kappa-factorizations were obtained. Several results were obtained on list-colorings, fractional colorings and greedy colorings of graphs. For example, a study of extensions of the classic theorem of Hall on systems of district representatives was applied to list colorings. Algorithmic methods were also developed for considering proper list-(multi) colorings. Network vulnerability was an issue studied in connection with the Shields-Harary number of a graph. This involves enemies removing weighted vertices at a certain cost, trying to break the graph into components of small weight, while defenders arrange the weights on the vertices to exact the greatest payment possible by the enemy.