极值和染色问题的一些新结果

发布时间：2020-10-23 03:17

　　 图论是离散数学的一个重要的分支,它在生产管理,军事,交通运输,计算机科学与技术,通信工程等领域都有着广泛的应用.1736年,Euler[14]发表的关于Konigsberg七桥问题的论文是图论领域的第一篇文章.后来,一些著名的图论问题相继被提出,如四色问题和中国邮递员问题等等.1878年,Sylvester[98]在《自然》上的一篇论文中首次提出了“图”这一名词.1936年,Konig[71]出版了第一本图论专著《有限图和无限图理论》,从此图论成为数学的一个独立的分支.一个图G定义为一个二元组(V(G),E(G)),记为G=(y(G),E(G)),其中V(G)是一个非空有限集,称为图G的顶点集；E(G)是定义在V(G)上的二元关系,称为图G的边集.本文所涉及到的图指的均是简单有限无向图.图G的补图用G来表示.我们分别用△(G)和δ(G)表示图G的最大度和最小度.图G的平均度为2|E(G)|/|V(G)|.图G的最大平均度mad(G),为G的所有子图的平均度的最大值.如果能将图G画在平面上,使得它的边仅在端点处相交,则称G是可平面图.本文主要研究图的极值问题和染色问题.在第一章,我们介绍了本文要用到的一些基本概念和符号.然后,对本文涉及到问题的背景,进展以及已知结果给出一个比较全面的综述.在本论文的第一部分(第二章,第三章和第四章),我们考虑与树的存在性相关的一些极值问题.极值图论是图论研究的一个重要领域,它起源于1941年Turan的文章[101].在该篇文章中他得到了不包含r阶完全图Kr的n阶图的最大边数,并确定了相应的极图.1978年,Bollobas[15]的关于极值图论问题的专著《极值图论》的问世标志着极值图论的研究已形成相对完整的理论.1998年,Chung和Graham[31]的著作搜集了Erdos在极值图论和图论其他课题中提出的尚未解决的问题,将极值图论的研究推向了一个新的高度.树是极小的连通图,是一类简单而又重要的图.1847年,Kirchhoff为了解电网络中一类线性方程组而提出了树这一概念,见[97].1857年,Cayley[25]在研究给定碳原子数为n的饱和碳氢化合物CnH2n+2的同分异构体时也发现了树,并提出了树的计数问题.此后,树在化学领域中发挥着日趋重要的作用.随着计算机科学的发展,树广泛应用于数据结构中,比如二叉查找树,堆,Trie树以及Huffman树等等.树是图的连通性理论中重要的子结构,一个图是连通的当且仅当其有支撑树.我们考虑的问题是：在什么条件下,图G包含所有的k阶树?显然,若δ(G)≥k-1,则G包含所有的k阶树.若δ(G)≥k-1,则G中的边分布较为均匀.若不考虑G中边的分布情况,G的平均度大于k-2,G能否包含所有的k阶树?设G为平均度大于k-2的n阶图,则△(G)≥k-1,那么G包含k阶星Sk.1959年,Erdos和Gallai[44]证明了G包含k阶路Pk.在此基础上,1965年,Erd6s和Sos[42]提出了如下猜想：Erdos-Sos猜想设G是一个n阶图.若G的边数e(G)n(k-2)/2,则G包含所有的k阶树.若δ(G)≤k-2但G至少有一半顶点的度至少为k-1,G能否包含所有的k阶树?Loebl猜想若G至少有一半顶点的度至少为n/2-1,则G包含所有的n/2阶树.Komlos和S6s把这个猜想推广到一般的k,见[43].Loebl-Komlos-Sos猜想设G是一个n阶图.若G至少有n/2个顶点的度至少为k-1,则G包含所有的k阶树.这两个猜想现在仍然没有被解决.在Bondy和Murty的著作《图论及其应用》中,Erdos-S6s猜想被列为尚未解决的问题12；在此书的第二版中,Erdos-S6s猜想被列为尚未解决的问题31,见[17,18].由此看来,要完全解决Erd6s-S6s猜想是非常困难的.在[70]中,Komlos和Simonovits指出Loebl-Koml6s-S6s猜想并不比Erdos-S6s猜想简单.在第二章,我们对Erdos-S6s猜想进行了研究.在2.1节,我们利用G中任意两个不相邻的顶点没有公共的非邻点,证明了若G的独立数为2,则Erdos-S6s猜想成立.这个结果改进了Li, Liu和Wang在文章[75]中的结果.在2.2节,我们利用可平面图的拓扑性质,证明了若G为可平面图,则Erdos-S6s猜想成立.此外,我们证明了若G为k+5阶可平面图,则百包含所有的k阶树.在第三章,我们对Loebl-Komlos-S6s猜想进行了研究,证明了若G的独立数为2,则Loebl-Komlos-S6s猜想成立.设G为n阶可平面图,由欧拉公式,我们有δ(G)≤5.Brinkmann和McKay[20]证明了若n≥12且n≠13,则存在最小度为5的n阶可平面图.在2.2节我们证明了若G为k+5阶可平面图,则G包含所有的k阶树.若k≥8且k≠9,则存在最小度为5的k+4阶可平面图G.由于△(G)=k-2,因而G不包含Sk,故界k+5是紧的.对任意给定的k阶树Tk≠Sk,界k+5是否仍然是紧的?特别地,对任意给定的Tk,若可平面图G不包含kl,界k+5是否仍然是紧的?G的最小阶数使得若G不包含kl,则G包含Tk即为Kl对Tk的平面Ram-sey数PR(Kl,Tk).设G1和G2为图,G1对G2的平面Ramsey数PR(G1,G2)为最小的正整数N使得任意N阶可平面图G,若G不包含G1,则G包含G2.Chvatal[32]证明了R(Km,Tn)=(m-1)(n-1)+1,其中Tn是任意的n阶树.在第四章,我们利用极大可平面图的拓扑性质和连通度等性质,确定了完全图对树的平面Ramsey数.在本论文的第二部分(第五章和第六章),我们研究两个加了某些限制条件的染色问题.图的染色理论起源于十九世纪中叶的四色问题,是图论研究的的传统领域之一.染色理论不仅具有重要的理论意义,而且具有很强的应用背景[67].它在组合最优化,交通流,网络设计和计算机理论等方面有着重要的应用.图的染色理论内容十分丰富,除了经典的点染色,边染色以及全染色以外,还有在此基础上添加其他约束所产生的一些特殊染色问题.设A表示k个颜色的集合.图G的一个k-点染色是从V(G)到A的一个映射φ.若G中相邻的顶点染不同的颜色,则称φ为正常的.图G的色数χ(G),为最小的整数k使得G有正常的k-点染色.对任意的图G,有χ(G)≤△(G)+1.由Brooks定理[21]知,若G既不是奇圈又不是完全图,则χ(G)≤△(G).图G的一个k-边染色是从E(G)到A的一个映射φ.若G中相邻的边染不同的颜色,则称φ为正常的.图G的边色数χ'(G),为最小的整数k使得G有正常的k-边染色.由Vizing定理[103]知,△(G)≤x'(G)≤△(G)+1.图G的一个k-全染色是从V(G)∪E(G)到A的一个映射φ.若G中相邻的或者相关联的两个元素染不同的颜色,则称φ为正常的.图G的全色数χ"(G),为最小的整数k使得G有正常的k-全染色.显然,χ"(G)≥△(G)+1.Molloy和Reed[77]证明了χ"(G)≤△(G)+1026.Vizing[103]和Behzad[12]分别独立给出了如下的全染色猜想：对任意的图G,有χ"(G)≤△(G)+2.Vijayaditya[102]和Rosenfeld[84]分别独立证明了△(G)≤3时,全染色猜想成立；Kostochka[72,73]证明了当△(G)=4,5时,全染色猜想成立；而当△(G)≥6时全染色猜想是否成立至今仍未得到证明.设φ是图G的边染色(或者是全染色),接下来我们考虑由与v相关联的边的颜色组成的集合或者加和(或者是由与v相关联的边的颜色和u的颜色组成的集合)导出的点染色问题.设φ为图G的一个正常的k-边染色.我们用Cφ(v)表示与点v相关联的边的颜色的集合,则映射φ:v→Cφ(u)是G的一个点染色,称为由φ导出的点染色.若φ为正常的,则称φ为G的k-邻点可区别边染色.图G的邻点可区别边色数χ'α(G),为最小的整数k使得G存在k-邻点可区别边染色.若G有邻点可区别边染色,则G没有孤立边.由于G的任意一个邻点可区别边染色也为G的正常的边染色,故xa'(G)≥x'(G).若G有相邻的最大度点,则χ'α(G)≥△(G)+1.2002年,Zhang,Liu和Wang[123]提出了邻点可区别边染色的概念并提出了如下猜想.EAVD猜想对于任意阶数至少为6的连通图G,xa'(G)≤△(G)+2.Hatami[53]利用概率的方法证明了若△(G)1020,则xa'(G)≤△(G)+300. Akbari,Bidkhori和Nosrati[4]证明了χ'α(G)≤3△(G).Zhang,Wang和Lih[124]把这个界改进到了5(△(G)+2)／2.Balister等人[7]证明了χ'α(G)≤△(G)+O(logx(G)).下面我们考虑更强的染色.设A：={1,2,...,k}表示k个颜色的集合且φ为图G的一个正常的k-边染色.我们用wφ(v)表示与点v相关联的边的颜色的加和,则映射φ:v→ωφ(v)是G的一个点染色,称为由φ导出的点染色.若φ为正常的,则称φ为G的k-邻和可区别边染色.图G的邻和可区别边色数χ'∑(G),为最小的整数k使得G存在k-邻和可区别边染色.若G有邻和可区别边染色,则G没有孤立边.由于G的任意一个邻和可区别边染色也为G的邻点可区别边染色,故x'∑(G)≥x'a(G).2013年,Flandrin等人[47]研究了圈,树,完全图,完全二部图的邻和可区别边色数,并提出了如下猜想：ENSD猜想设G是一个阶数至少为3的连通图.若G≠G5,则χ'∑(G)≤△(G)+2.Flandrin等人[47]证明了χ'∑(G)≤Przybylo[82]利用组合零点定理证明了x'∑(G)≤2△(G)+Col(G)-1≤3△(G),其中col(G)是图G的染色数,定义为使得G有一个每个顶点的前面只能有少于k个邻点的点排序的最小整数k.最近,Przybylo[83]给出了χ'∑(G)的一个渐进上界并证明了x'∑(G)≤(1+o(1))△(G).图的邻和可区别边染色和著名的1-2-3猜想有着重要的联系.设A：={1,2,...,k}表示k个颜色的集合,且φ为图G的一个k-边染色.我们用wφ(v)表示与点v相关联的边的颜色的加和,则映射φ:v→χ(v)是G的个点染色,称为由φ导出的点染色.若φ为正常的,则称φ为G的k-边权点染色.2004年,Karonski,Luczak和Thomason[69]研究了图的边权点染色,并提出如下的猜想.1-2-3猜想每个阶数至少为3的图G,都是3-边权点染色的.Karonski,Luczak和Thomason[69]证明了若χ(G)=3,则1-2-3猜想成立.Kalkowski,Karonski和Pfender[68]证明了每个阶数至少为3的图,都是5-边权点染色的.在第五章,我们讨论了图的邻和可区别边染色.设G为没有孤立边的图.在5.1节,我们利用权转移的方法证明了若mad(G)8/3,则x'∑(G)≤max{△(G)+ 1,7}；若mad(G)3,则x'∑笔(G)≤max{△(G)+2,7)这个结果改进了Dong, Wang和Zhang在文章[37]中的结果.在5.2节,我们分析了2-退化图的结构性质,证明了若G为2-退化图,则x'∑(G)≤max{△(G)+2,7).2005年,Zhang等人[122]把邻点可区别边染色推广到了邻点可区别全染色.设φ为图G的一个正常的k-全染色.我们用Cφ(v)表示点v的颜色和所有与点v相关联的边的颜色组成的集合,则映射φ:v→Cφ(v)是G的一个点染色,称为由φ导出的点染色.若φ为正常的,则称φ为G的k-邻点可区别全染色.图G的邻点可区别全色数χ"α(G),为最小的整数k使得G有k-邻点可区别全染色.由于G的任意一个邻点可区别全染色也为G的正常的全染色,故χ"α(G)≥χ"(G).若G有相邻的最大度点,则χ"α(G)≥△(G)+2Zhang等人[122]提出了如下猜想.TAVD猜想设G是一个图,则χ"α(G)≤△(G)+3.Zhang等人[122]证明了G为路,圈,扇,轮,树,完全图,完全二部图时,TAVD猜想成立.由图的点染色,边染色和邻点可区别全染色的定义知xa"(G)≤x(G)+χ'(G).由Brooks定理和Vizing定理知,xa"(G)≤△(G)+△(G)+1=2△(G)+1. Huang,Wang和Yan[64]把这个界改进到了2△(G).在第六章,我们讨论了图的邻点可区别全染色,证明了xa"(G)≤x(G)+△(G).这个结果改进了[64]中的结果.此外,我们证明了若χ(G)=3,则TAVD猜想成立.
【学位单位】：南京大学
【学位级别】：博士
【学位年份】：2015
【中图分类】：O157.5
【文章目录】：
摘要
Abstract
Notations
Chapter 1 Introduction
    1.1 Notations and definitions
    1.2 Problems on extremal graph theory
        1.2.1 Erdos-Sos Conjecture and Loebl-Komlos-Sos Conjecture
        1.2.2 Planar Ramsey numbers
    1.3 Problems on graph Colorings
        1.3.1 Neighbor sum distinguishing edge colorings
        1.3.2 Adjacent vertex distinguishing total colorings
Part Ⅰ Results on extremal graph theory
    Chapter 2 On the Erdos-Sos Conjecture
        2.1 Erdos-Sos Conjecture for graphs with independence number two
            2.1.1 Motivation and results
            2.1.2 Preliminary lemmas
            2.1.3 Proof of the main result
        2.2 Erdos-Sos Conjecture for graphs whose complements are planar
            2.2.1 Motivation and results
            2.2.2 Preliminary lemmas
            2.2.3 Proof of the main result
    Chapter 3 Loebl-Komlos-Sos Conjecture for graphs with independence number two
        3.1 Motivation and results
        3.2 Proof of the main result
    Chapter4 Complete graph-tree planar Ramsey numbers
        4.1 Motivation and results
        4.2 Preliminary lemmas
3,S_n）'>        4.3 PR（K₃,S_n）
3,T_n）with △（T_n）≤n-2'>        4.4 PR（K₃,T_n）with △（T_n）≤n-2
        4.5 Existence of double-star like trees
n-2（k,l）with k+l=n-4'>            4.5.1 DS_n-2（k,l）with k+l=n-4
n-2（k,l）with k+l≤n-5 and k≥3'>            4.5.2 DS_n-2（k,l）with k+l≤n-5 and k≥3
n-2（k,l）with k+l≤n-5 and k≤2'>            4.5.3 DS_n-2（k,l）with k+l≤n-5 and k≤2
        4.6 Existence of all trees
n-2 with n-6≤△(T_n-2)≤n-δ-1'>            4.6.1 T_n-2 with n-6≤△(T_n-2)≤n-δ-1
n-2 with n≥15 and △(T_n-2)=n-7'>            4.6.2 T_n-2 with n≥15 and △(T_n-2)=n-7
n-2 with △(T_n-2)≤n-δ-1'>            4.6.3 T_n-2 with △(T_n-2)≤n-δ-1
m,T_n）with m≥4 and△（T_n）≥n-3'>        4.7 PR（k_m,T_n）with m≥4 and△（T_n）≥n-3
m,T_n）with m≥4 and△（T_n）≤n-4'>        4.8 PR（K_m,T_n）with m≥4 and△（T_n）≤n-4
Part Ⅱ Results on graph colorings
    Chapter 5 On the neighbor sum distinguishing edge colorings
        5.1 Neighbor sum distinguishing edge colorings of sparse graphs
            5.1.1 Motivation and results
            5.1.2 Preliminary lemmas
            5.1.3 Proof of the main results
        5.2 Neighbor sum distinguishing edge colorings of 2-degenerate graphs
            5.2.1 Motivation and result
            5.2.2 Preliminary lemmas
            5.2.3 Proof of the main result
    Chapter 6 Upper bound on adjacent vertex distinguishing total chromatic number
        6.1 Motivation and results
        6.2 Proof of the main result
Bibliography
Acknowledgements
Awards, Foundations and Publications

【参考文献】

相关期刊论文 前5条

1 单而芳，孙良;2－退化图的全色数[J];北京理工大学学报;1995年04期

2 ;On adjacent-vertex-distinguishing total coloring of graphs[J];Science in China,Ser.A;2005年03期

3 黄丹君;王维凡;;高度平面图的邻点可区别全染色[J];中国科学:数学;2012年02期

4 周兵;A N OTE ON THE ERD?S-S?S CONJECTURE[J];Acta Mathematica Scientia;1984年03期

5 ;The Erd?s-Sós Conjecture for Graphs Whose Complements Contain No C_4[J];Acta Mathematicae Applicatae Sinica(English Series);2004年03期

本文编号：2852485