In this statement I will concentrate on describing some of the topics that I have worked on and how I imagine future work might proceed. I am also interested in a wider variety of problems, which I will briefly discuss towards the end. We consider only simple graphs.

An extremal problem will often ask for the maximum size substructure of a given type that can be guaranteed to appear in graphs of a given class. Albertson and Berman [2] conjectured that every planar graph has an induced subgraph that is a forest and has at least half of the vertices. (This would directly imply that a planar graph contains an independent set with at least a quarter of the vertices, without using the Four-Color Theorem.) Akiyama and Watanabe [6] gave examples showing that this would be best possible. Borodin [8] proved the best known lower bound of 2/5 on this ratio by proving that the vertex set of a planar graph may be partitioned into five independent sets, any two of which together induce a forest. Akiyama and Watanabe [6] conjectured that every bipartite planar graph has an induced subgraph that is a forest and has at least 5/8 of the vertices, and gave examples to show that this would be best possible.

Hosono [12] proved that every outerplanar graph has an induced subgraph that is a forest and has at least 2/3 of the vertices. This bound is best possible, as shown by the square of a path with n vertices or by a disjoint union of triangles.

A linear forest is a graph in which every component is a path; equivalently, it is a graph with no cycles and no vertices of degree at least 3. Poh [19] showed that every planar graph has an induced linear forest using at least 1/3 of the vertices, by proving that the vertex set of a planar graph can be partitioned into three sets inducing linear forests, which was conjectured by both Broere-Mynhardt [11] and Mihók [18]. Chappell conjectured that every planar graph has an induced linear forest using more than 4/9 of the vertices, and he found examples to show that this is best possible. In addition to improving the best known lower bound for maximum induced forests in planar graphs, this would also strengthen Albertson's result [1] that a planar graph G has an independent set with at least 2/9 of the vertices, which was proved independently of the Four-Color Theorem.

These results suggest the analogous question for linear forests in outerplanar graphs. Three groups ([3], [11], [18]) independently showed that the vertex set of an outerplanar graph can be partitioned into two sets, each of which induces a linear forest. This proves a lower bound of 1/2 on this ratio for the largest induced linear forest. Chappell conjectured that every outerplanar graph has an induced linear forest with more than 4/7 of the vertices, and he found examples to show that 4/7 is the best possible ratio.

I showed that every n-vertex outerplanar graph has an induced subgraph with at least (4n + 2)/7 vertices that is a linear forest. Furthermore, this bound is sharp. In order to facilitate the induction, I actually proved a slightly stronger result: Roughly speaking, given an outerplanar graph and a certain subset S of its vertices, there is a induced linear forest that is large and that contains S. When allied with discharging methods, the same technique shows promise for proving Chappell's conjecture that every planar graph has an induced linear forest using more than 4/9 of the vertices. This conjecture seems to be much harder than the result of Albertson that it generalizes, in that it is more difficult to find reducible configurations. Possibly I can also adapt the ideas directly to the conjectures about induced forests in planar and bipartite planar graphs.

Graph coloring has applications in resource allocation, and the possibility of a restricted list of resources for each user motivates the notion of list coloring. For each vertex v in a graph, let L(v) be a list of colors available for v. A list coloring from the given collection of lists is a proper coloring c such that c(v) is chosen from L(v). A graph is k-choosable if every assigment of k-element lists to its vertices permits a list coloring. List coloring has attracted much attention in the last decade (see Tuza [20]), and I've been working on two variations of it.

Equitable coloring is another very active area of research (see Lih [17]). Kostochka, West, and I [16] have combined these notions: An n-vertex graph is equitably k-choosable if every assigment of k-element lists to its vertices permits a list coloring such that each color class has size at most the ceiling of n/k. We seek the least k such that G is equitably j-choosable for all jgreater than k.

We have determined the least such k in terms of maximum degree for trees, interval graphs, and graphs with maximum degree 3. We also have an upper bound for outerplanar graphs in terms of maximum degree. The proofs of the upper bounds are modifications of a general inductive technique in which we reserve a set S of k appropriate vertices and show that an equitably chosen coloring for G-S can be extended to G using distinct colors from the lists on S. I believe that we can extend some bounds for outerplanar graphs to graphs with tree-width at most 3. (Tree-width is defined below.) Also I will investigate the asymptotic behavior for graphs in general, in terms of maximum degree.

Sum list coloring number was recently defined by Garth Isaak ([14], [15]). For list sizes given by a function f, a graph is f-choosable if for every collection of lists with sizes given by f there is a proper coloring using colors from the lists. The sum list coloring number is the minimum sum of the values of a function f on V(G) such that G is f-choosable. (From this viewpoint, the ordinary choice number is the minimum constant function f such that G is f-choosable.)

Isaak showed that if G is the line graph of a tree, then its sum list coloring number is m+n, where m and n denote the number of edges and vertices of G [15]. I noticed that m+n is an easy upper bound for the sum list coloring number for every graph G. I have extended Isaak's result, showing that equality holds for graphs in which each block is a cycle or a clique. I'm currently trying to show that the sum list coloring number equals m+n in the larger family of chordal graphs. I plan to investigate the difference between the sum list coloring number and m+n.

End-to-end communication considers problems of sending messages from a sender S to a receiver R through an asynchronous, unreliable network, such as the internet. The following model was introduced by Fich in [9]; she explored it further with several coauthors in [4] and [5]: Consider the problem of transmitting a single message from S to R through a network in which edges may fail and cannot recover. We can assume that there is at least one SR-path without failed edges, but we do not know which path it is. The aim is to design a protocol that ensures that a message sent by S will be received by R (no matter which edges have failed) without generating an infinite number of messages in the process.

Fich, Kündgen, Ramamurthi and I [10] gave a forbidden rooted-minor characterization of the family of networks in which this is possible, and we give the protocol. We have also shown that there is a forbidden rooted-minor characterization for the case when we can attach a fixed-length header containing routing information to the message. We also discussed the algorithmic consequences of these characterizations.

In the proofs, we bound the tree-width of graphs for which a good protocol exists. For the characterizations, we use a tree decomposition of small width to investigate the structure of such a graph. A tree decomposition of a graph G imposes a tree-like structure on it by specifying certain vertex subsets corresponding to the nodes of a tree T such that 1) each edge of G is covered by a vertex subset, and 2) the sets containing a given vertex of G correspond to a subtree of T. The width of a tree decomposition is one less than the maximum size of these vertex sets, and the tree-width of a graph is the minumum width of its tree decompositions. (Forests are the graphs of tree-width 1, and outerplanar graphs have tree-width 2.) A nice survey of the recent history of these concepts is given by Bodlaender [7].

I would like to apply my experience with tree decompositions to other algorithmic questions.

Finally I will mention some other directions I want to pursue. I'm interested in topological graph theory, including links between topology and graph theory, connectivity, and the theory of graph minors. Coloring problems lead naturally to many sorts of extremal problems for graphs and hypergraphs. In addition, I plan to begin studying several problems in discrete geometry this year.

[ 1 ] Albertson, M.O., A lower bound for the independence number of a planar graph. J. Combin. Theory Ser. B 20 (1976), no. 1, 84-93.

[ 2 ] Albertson, M.O., Berman, D.M., A conjecture on planar graphs, in Graph Theory and Related Topics, Edited by J. A. Bondy and U. S. R. Murty. Academic Press (1979), 357.

[ 3 ] Akiyama, J., Era, H., Gervacio, S.V., Watanabe, M., Path chromatic numbers of graphs. J. Graph Theory 13 (1989), no. 5, 569-575.

[ 4 ] Adler, M., Fich, F.E., The Complexity of End-to-End Communication in Memoryless Networks, 18th Annual ACM Symposium on Principles of Distributed Computing, May 1999, pages 239-248.

[ 5 ] Adler, M., Fich, F.E., Goldberg, L.A. and Paterson, M., Tight Size Bounds for Packet Headers in Narrow Meshes, Proceedings of the Twenty Seventh International Colloquium on Automata, Languages and Programming (ICALP), July 2000.

[ 6 ] Akiyama, J., Watanabe, M., Maximum induced forests of planar graphs. Graphs and Combinatorics 3 (1987), 201-202.

[ 7 ] Bodlaender, H.L., A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science 209 (1998), 1-45.

[ 8 ] Borodin, O.V., A proof of B. Grünbaum's conjecture on the acyclic 5-colorability of planar graphs (Russian). Dokl. Akad. Nauk SSSR 231 (1976), no. 1, 18-20. English translation: Soviet Math. Dokl. 17 (1976), no. 6, 1499-1502.

[ 9 ] Fich, F.E., End-to-end Communication, Proceedings of the 2nd International Conference on Principles of Distributed Systems, Amiens, France, 1998, pages 37-43.

[ 10 ] Fich, F.E., Kündgen, A., Pelsmajer, M.J., Ramamurthi, R., Graph Minors and Reliable Single Message Transmission, in process.

[ 11 ] Broere, I., Mynhardt, C.M., Generalized colorings of outerplanar and planar graphs, in Graph Theory with Applications to Algorithms and Computer Science, Edited by Y. Alavi, G. Chartrand, L. Lesniak [L. M. Lesniak-Foster], D. R. Lick and C. E. Wall. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York (1985), 151-161.

[ 12 ] Chappell, G.G., Personal Correspondence.

[ 13 ] Hosono, K., Induced forests in trees and outerplanar graphs. Proc. Fac. Sci. Tokai Univ. 25 (1990), 27-29.

[ 14 ] Isaak, G., Sum List Coloring 2 by n Arrays. Manuscript.

[ 15 ] Isaak, G., Sum List Edge Coloring Trees. Manuscript. [ 16 ] Kostochka, A.V., Pelsmajer, M.J., West, D.B., Bounds on equitable choosability for several classes of graphs. In preparation.

[ 17 ] Lih, Ko-wei, The equitable coloring of graphs, in Handbook of combinatorial optimization, Vol. 3, Edited by Ding-Zhu Du and Panos M. Pardalos. Kluwer Academic Publishers, Boston, MA, (1988), 543-566.

[ 18 ] Mihók, P., On vertex partition numbers of graphs, in Graphs and Other Combinatorial Topics, Edited by M. Fiedler. B. G. Teubner Verlagsgesellschaft (1983), 183-188.

[ 19 ] Poh, K.S., On the linear vertex-arboricity of a planar graph. J. Graph Theory 14 (1990), no. 1, 73-75.

[ 20 ] Tuza, Z., Graph coloring with local constraints - a survey. Discussiones Mathematicae. Graph Theory 17 (1997), no. 2, 161-228.