Domination and Colouring Games in Graphs

我的研究计划的主要目标和长期目标是发展组合学知识，重点研究正确着色与图的独立性和控制性之间的联系。短期内，我努力在解决新的、创新的问题和研究过的经典问题之间找到平衡。最近在这个方向上的许多创新都是以动态和离散时间图过程和游戏的形式来陈述的。该计划的另一个目标是培训高素质的人员。重要的是，更多的加拿大年轻人拥有高等数学的技能和知识。培训是我研究计划中不可或缺的一部分，主要是通过吸引顶尖的年轻研究人员参与数学研究项目(本科生和硕士学生)。**着色的概念通过简单但困难的问题吸引了许多人的兴趣。例如，一张地图可以用四种颜色来着色，这样共享边界的国家就会得到不同的颜色吗？这个问题一直是图论概念的核心。这项研究计划的一部分着眼于地图颜色的变化，以寻求在该领域获得更强的理论知识。蜂窝网络等行业应用着色理论，将购买渠道的成本降至最低。具有不同程度的网络干扰的信道分配问题目前还没有得到很好的理解，将在本次调查中进行研究。**着色理论与独立和统治密切相关。在这些主题之间寻找新的联系是本次调查的主要兴趣所在。我们将探索色彩、独立性和支配性之间已知的极端关系。为了帮助开发新的技术，将通过将我们的注意力限制在较小的子图类来改进某些连接。**动态和离散时间过程可以用来为许多具有现实应用程序的有趣游戏建模。在灾难或紧急情况下部署移动资源中心，可以认为是“永恒的统治”。这些移动单位的位置和移动方式必须使它们能够对任何一系列紧急情况作出充分反应。在这种情况下，最大限度地利用资源往往是至关重要的。“消防员问题”模拟了火势在地图上的蔓延和控制。我们的主要目标是确定保护地图一定比例所需的最低资源。另一个目标是将火灾在被控制之前烧毁的节点数量降至最低。这一目标可能会因政治需要而变得复杂，从而产生额外的限制。这个问题也可以被认为是通过网络传播的病毒，或者是通过人群传播的谣言。**有点令人惊讶的是，永恒支配的资源中心数量的界限与色彩和独立性密切相关。消防员问题的答案通常使用与地图着色和通道分配问题相同的技术来找到。**该研究计划建立在这些领域既定成功的基础上，为组合数学的探索和进步做出强有力的贡献。这项提议的另一个影响是预计总部将参与这些项目。将学生纳入上述问题的机会包括在HQP培训计划中。任何项目的成功完成都将为组合学社区提供感兴趣的解决方案，并将加深我们对着色、独立性和支配性以及这些概念之间的联系的理解。希望作为这一研究计划的一部分开发的方法将成为未来学者的有用工具。

The principal objective and long term goal of my research program is the advancement of combinatorics knowledge with a focus on studying the connections between proper colourings and independence and domination in graphs. For the short term, I strive to find a balance between working on new, innovative problems and classical, well studied questions. Many of the recent innovations in this direction are stated in the form of dynamic and discrete-time graph processes and games. An additional objective of this program is the training of highly qualified personnel. It is important that more young Canadians have the skills and knowledge for advanced mathematics. Training is an integral part of my research program, primarily by attracting top young researchers to mathematical research projects (undergraduate and Master's students).**The concept of colouring captures the interest of many via simply stated, but difficult questions. For example, can a map be coloured with four colours so that countries sharing a border receive different colours? This question has been central in the concept of Graph Theory. Part of this research program looks at variations of map colourings in a quest to gain a stronger theoretical knowledge in the field. Industries, such as cellular networks, apply the theory of colouring to minimize the cost of purchasing channels. Channel assignment problems, with varying levels of network interferences, are not currently well understood and will be studied in this investigation. **The theory of colouring is intimately related to independence and domination. Finding new connections between these topics is of primary interest in this investigation. The extremes of known relationships between colouring, independence and domination will be explored. To help develop new techniques, certain connections will be refined by restricting our attention to a smaller, subclass of graphs.**Dynamic and discrete time processes can be used to model many fascinating games that have real-life applications. One can think of "eternal domination" as deploying mobile resource centers during a disaster or emergency situation. These mobile units have to be situated and moved in such a way that they adequately respond to any sequence of emergencies. It is often critical to maximize the use of resources in such a situation. The "firefighter problem" models the spread and containment of fire over a map. Our main goal is to determine the minimum resources needed to protect a certain proportion of the map. Another goal is to minimize the number of nodes a fire burns before being contained. This goal can be complicated by political needs which produce additional constraints. The problem can also be thought of as a virus spreading through a network, or a rumour through a population. **Somewhat surprisingly, bounds on the number of resource centers in eternal domination are closely related to colourings and independence. Answers to questions poised in the firefighter problem are often found using the same techniques as the map colouring and channel assignment problem. **The research program builds on the established success in these areas to make strong contributions to the exploration and advancement of Combinatorics. An additional impact of this proposal is the anticipated involvement of HQP in these projects. Opportunities for student inclusion in the above problems are included in the HQP Training Plan. Successful completion of any of the projects will provide a solution of interest to the combinatorics community and will further our understanding of colouring, independence and domination and the connections between these concepts. It is hoped that methods developed as part of this research program will be useful tools for future scholars.