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
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=677676
• 关键词: 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的所有节点着色，使得L(V)中的每个顶点v都被赋予一种颜色，并且使得相连的节点接收不同的颜色。这种类型的问题出现在电台和电视台的频率分配中，并有许多其他应用。托马森证明了，如果N是一个平面网络，且每个L(V)至少有5种颜色，则存在所描述的着色。*我们对推广托马森定理很感兴趣。特别地，如果我们将一个5-列表可着色图H附加到一个平面图的一个面上会发生什么？5-list有色有障碍；有哪些障碍？我们能描述结果总是5列表可染的有趣的图族H吗？*