论文部分内容阅读
图的染色理论起源于著名的“四色猜想”,是图论的一个重要分支。研究图的染色不仅有重大的理论意义,而且在理论计算机科学、管理科学、信息科学等领域均有很强的实际应用背景。图的整数流问题,其产生和发展与图的染色密切相关,亦是图论的研究热点之一。本文主要由四个章节组成,主要内容如下:在第一章,我们首先给出与本文相关的基本概念和记号,接着介绍本文的研究背景和研究意义,国内外在这方面的代表性研究成果及研究现状。在第二章,我们研究了特殊符号图的处处非零整数流问题。1983年,Bouch[13]最早开始研究符号图的整数流并提出著名的猜想:每个有流的符号图都存在处处非零6-流。围绕这个猜想,国内外诸多学者展开广泛的研究。到目前为止,该猜想尚未解决。本章研究了符号轮图、符号扇图和极大外平面符号图的整数流问题,证实了对这些特殊的符号图,Bouch猜想是正确的。具体结果如下:1.若(G,σ)是有流的符号轮图,则除了一个特殊图之外,(G,σ)有处处非零4-流。2.若(G,σ)是有流的符号扇图,则(G,σ)有处处非零4-流。3.若(G,σ)是2-连通的有流的极大外平面符号图,则它有处处非零4-流。在第三章,我们研究了符号平面图的3-色问题。该部分的研究主要来源于Erdos针对Steinberg猜想提出的一个问题:是否存在一个正整数k,使得不含4-至k-圈的平面图是3-可染的?我们考虑了符号图中的Erdos问题,证明了每个不含4-8圈的符号平面图是3-可染的。第四章主要研究图的强边染色问题。我们从图的最大平均度这一角度出发来研究图的强边色数,得到了若干稀疏图的强边色数的上界,具体结果如下:设图G满足△ ≥ 5,则:1.若 mad(G)<30/11,则 χs’(G)≤3△-2。2.若 mad(G)<20/7,则 χs’(G)≤3△-1。3.若 mad(G)<3,则 χs’(G)≤3△。我们的结果3推广了 Choi等人在文[19]中的结果,并简化了他们的证明。此外,结果3亦改进了Bensmail等人[5]和Ruksasakchai和Wang[50]的相关结果。