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

图形的交叉数、图形的列表着色、图形中的流

• 批准号: RGPIN-2019-04156
• 负责人: Richter, Bruce
• 金额: $ 1.53万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=749578
• 关键词: Crossing; Numbers; Graphs; List; Colourings

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?

数据的呈现方式，特别是数据集各部分之间的关系，有助于数据的分析。如果数据显示在一个页面上，则一些数据点之间可能存在联系，表明它们彼此的重要性。为了清晰地表示数据，我们可以尽量减少图中相互交叉的这些连接的数量。在计算机芯片的构造中也有类似的问题：芯片上不同节点之间的连接不应该交叉，我们不希望出现短路。关于网络的一般交叉数问题，有两个问题：1)如何在平面上画一个网络，使相互交叉的连接对很少？2)这个网络的最小穿越次数是多少？一个重要的例子是完整网络，其中每一对节点都是连接的。在近60年的时间里，根据网络中节点的数目n，已经有了一个最小数目的推测值。我们只知道这个猜想在n≤12时成立。我的一些工作集中在寻找一个完整网络的图的一般性质，如果这个图是一个具有最少交叉数的图，那么这个图必须成立。通过这项工作，我们希望大大改善验证猜想的前景，既适用于更大的n值，最终目标是适用于所有n。我们在完整网络上的工作已经导致了对更一般网络的绘制的影响。在一个完整的网络图中，一些关于边如何相交的自然考虑与几何考虑完全一致，比如：可以在平面上画，这样每条边都是一条直线，或者可以在球体上画，这样每条边都包含在一个大圆中。有趣的是，这些几何条件的概括可以描述一般网络的图，而不仅仅是完整的网络。因此，我们可以在一般网络的研究中扩展几何考虑的范围。在两个不同方向中的第一个，我们感兴趣的是一个网络N，这样每个节点v都有一个预先分配的颜色集L(v)。我们希望给N的所有节点上色，使得每个顶点v在L(v)中被赋予一种颜色，并且连接的节点接收到不同的颜色。这类问题出现在无线电和电视台的频率分配中，并有许多其他应用。Thomassen证明了如果N是一个平面网络，并且每个L(v)至少有5种颜色，则存在描述的一种着色。我们对推广托马森定理的有效性很感兴趣。特别是，如果我们将一个5-list可着色的图H附加到一个平面图的面上会发生什么？5-list的可着色性存在障碍；它们是什么？我们能否描述一些有趣的图族H，其结果总是5-list- colorable ？