Subgraph extension problem: structures, characterizations and its connection with edge-weighting coloring problems

子图扩展问题：结构、表征及其与边加权着色问题的联系

• 批准号: RGPIN-2014-05317
• 负责人: Yu, Qinglin
• 金额: $ 0.8万
• 依托单位: Thompson Rivers University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=669448
• 关键词: Subgraph; extension; problem; structures; characterizations

Subgraph extension and graph coloring problems* Graph Theory is an old but re-born and energized branch of mathematics. It has grown rapidly since the 1960's with its applications spreading to Physics, Biology and Operations Research, in particular to Computing Science and communication networks. Often graphs are used as a working frame for various scientific investigations. In particular, Computing Science has provided many interesting problems for Graph Theory to grow. More recently, Graph Theory has become a useful instrument for the study of gene sequences, environment sustainability, management science and logic designing. * The proposed program is to expand our knowledge on graph factors, subgraph extension and its connection to other combinatorial topics. The objectives are to acquire knowledge, both for research and HQP training in three ways:* 1) To understand the structures of subgraph extension graphs (i.e., (Y, H)-extendable graphs) by developing a decomposition procedure for the purpose of general recursive arguments. Such a decomposition will be vital for the design of efficient algorithms to recognize and to construct the family of such graphs. This work involves to generalize the existing techniques and methods, and to create new analysis tools for the general framework and abstract models. * 2) The research will deliver a more consistent and universal framework for the potential applications of subgraph extension to other combinatorial problems and other mathematical branches. The concept, (Y, H)-extendable graphs, is a well-defined framework, which not only consolidate many well-known concepts (e.g., factor-critical graph, bicritical graphs and defect-d matching) together and also maintain the basic properties of its sub-classes. This enables us to simplify many of the previous proofs and establish closer connections to other graph theory problems. * 3) In our proposal, we have stated many closely related and well-defined problems. These problems have different levels of difficulties, from conjectures and open problems, to generalization of known results and construction of specified classes of graphs; we also carefully select and blend the problems in proposal by considering our short-term and long-term objectives. The problems proposed will fulfill my vision in the study of subgraph extension and also provide opportunities for involvement of undergraduate and graduate students to engage in creation, exploration and experiencing rigorous research.

子图扩展和图着色问题* 图论是一个古老但重生且充满活力的数学分支。自 20 世纪 60 年代以来，它发展迅速，其应用扩展到物理、生物学和运筹学，特别是计算科学和通信网络。图表经常被用作各种科学研究的工作框架。特别是，计算科学为图论的发展提供了许多有趣的问题。 最近，图论已成为研究基因序列、环境可持续性、管理科学和逻辑设计的有用工具。 * 拟议的计划是扩展我们对图因子、子图扩展及其与其他组合主题的联系的知识。目标是通过三种方式获取知识，用于研究和 HQP 培训：* 1) 通过开发用于一般目的的分解程序来理解子图扩展图（即 (Y, H)-可扩展图）的结构递归参数。 这种分解对于设计有效的算法来识别和构建此类图族至关重要。这项工作涉及概括现有的技术和方法，并为通用框架和抽象模型创建新的分析工具。 * 2）该研究将为子图扩展在其他组合问题和其他数学分支的潜在应用提供一个更加一致和通用的框架。 (Y, H)-可扩展图的概念是一个定义明确的框架，它不仅将许多众所周知的概念（例如因子关键图、双临界图和缺陷-d 匹配）整合在一起，而且还保持了基本的其子类的属性。这使我们能够简化之前的许多证明，并与其他图论问题建立更紧密的联系。 * 3）在我们的提案中，我们陈述了许多密切相关且明确定义的问题。这些问题具有不同程度的难度，从猜想和开放问题，到已知结果的概括和指定类别图的构造；我们还考虑到我们的短期和长期目标，仔细选择和融合提案中的问题。 提出的问题将实现我对子图可拓研究的愿景，也为本科生和研究生提供参与创造、探索和体验严谨研究的机会。