Crossing Numbers of Graphs, List Colourings of Graphs, Flows in Graphs

点击翻译按钮获取中文摘要

How data is presented, especially the relations between the parts of the data set, can help in the analysis of the data. If the data is presented on a page, there may be connections between some of the data points indicating their significance to each other. To make the presentation of the data clear, we might try to minimize the number of these connections that cross each other in the diagram. There is a similar issue in the construction of a computer chip: the connections between the different nodes on the chip should not cross, we do not want a short circuit.******Here are two problems about the general crossing number problem of a network: 1) How can we draw a network in the plane so as to have few pairs of connections that cross each other? 2) What is this minimum number of crossings for this network?******One important example is the complete network, in which every pair of nodes is connected. For nearly 60 years, there has been a conjectured value for the minimum number, depending on the number n of nodes in the network. We only know the conjecture is true for n at most 12. Some of my work focusses on finding general properties of a drawing of a complete network that must hold if the drawing is to be one with a minimum number of crossings. With this work, we hope to substantially improve the prospects for verifying the conjecture both for larger values of n, with the ultimate goal being for all n.******Our work on complete networks has led to implications for drawings of more general networks. Some natural considerations about how edges cross in a drawing of complete network correspond exactly with geometric considerations like: the drawing can be made in the plane so that every edge is a straight line segment or the drawing can be made in the sphere so that every edge is contained in a great circle. What is interesting is that generalizations of these geometric conditions can describe drawings of general networks, not just complete ones. Thus, we can extend the range of geometric considerations in the study of general networks.******In the first of two different directions, we are interested in a network N such that each each node v has a preassigned set L(v) of colours. We wish to colour all the nodes of N such that each vertex v is assigned a colour in L(v) and such that connected nodes receive different colours. This type of problem arose in the assignment of frequencies for radio and television stations, and has many other applications. Thomassen proved that if N is a planar network and each L(v) has at least 5 colours, then there is a colouring as described. ******We are interested in extending the validity of Thomassen's Theorem. In particular, what happens if we attach a 5-list-colourable graph H to a face of a planar graph? There are obstructions to 5-list-colourability; what are they? Can we describe interesting families of graphs H for which the result is always 5-list-colourable?*****