Print

最大度较大的平面图的无圈边染色

论文摘要

图可以作为构造大量数学模型的有利工具.对图论的研究已经有两百多年的历史,其中图染色理论在图论研究中占有重要的地位,图的染色理论在最优化,计算机理论,网络设计,Hessians矩阵的计算等方面都有着重要的应用.本文旨在讨论具有较大的最大度的平面图的无圈边染色问题.用V（G）和E（G）分别表示图G的顶点集和边集.图G的一个正常的k-边着色是一个映射φ:E（G）→{1,2,A,k},使得任何相邻的两条边着不同的颜色.如果图G的一个正常的k-边着色不含2-色圈,则称该着色为无圈的.图G的无圈边着色中最小的边着色的数目,称为G的无圈边色数,记为Xa（G）.无圈着色问题作为一般染色问题的推广可用来有效的计算Hessians矩阵：如果已知Hessians矩阵是稀疏的和对称的,用有限差分方法来计算Hessians矩阵时可以转化为图的无圈染色问题.在2001年,Alon,Sudakov和Zals提出下列猜想：对任意图G,都成立△（G）≤χα（G）≤△（G）+2本文将通过三个章节,对具有较大的最大度的平面图,我们将给出这类图的无圈边色数的某些界.在第一章我们首先介绍一些图论中的基本概念和定义并给出无圈边染色问题的历史和进展,还给出本文的主要结论.在第二章,通过组合方法和局部充放点技术考察不包含相交三角形的平面图的无圈边色数,从而得到无圈边色数的两个界.在2.1节中,我们证明了设G是最大度为△（G）的平面图,若G不包含4-圈和相交三角形,则za（G）≤△（G）+3.在2.2节中,我们证明了：设G是最大度为△（G）≥12的平面图,若G不包含相交三角形,则x0（G）≤△（G）+4.在第三章,我们讨论了不包含相邻三角形的平面图的无圈边着色问题.在3.1节中,我们证明了对于最大度是△（G）≥18的平面图G,若G不包含相邻三角形,则x0（G）≤△（G）+5.在3.2节中,我们给出了一些需要进一步研究的问题.

论文目录

  • 中文摘要
  • Abstract
  • Contents
  • Chapter 1 Introduction
  • 1.1 Basic Terminologies
  • 1.2 Main Results
  • Chapter 2 Some Results about Planar Graphs without Intersecting Triangles
  • 2.1 Planar Graph without 4-Cycles and Intersecting Triangles
  • 2.2 Planar Graph without Intersecting Triangles with Large Maximum Degree
  • Chapter 3 A Result about Planar Graphs without Adjacent Triangles
  • 3.1 Planar Graph without Adjacent Triangles and with Large Maximum Degree
  • 3.2 Problem for Further Research
  • References
  • 致谢
  • 个人简历、在学期间的研究成果及发表的学术论文

    • 相关论文文献

    本文来源: https://www.lw50.cn/article/b5eed67913d89ff37e0c238e.html