论文摘要
横贯理论是超图理论研究的主要内容之一.图的团横贯是超图中横贯概念的一种特例,同时也是组合优化的研究重要对象之一,它在网络拓扑设计中具有广泛的应用,其次对深刻揭示图的结构具有重要意义.与图的团横贯和图的染色密切相关的另一个概念是图的团染色,与图的顶点染色相比,由于团染色中没有临界图的概念,其研究更加复杂.本文侧重研究了某些图类的团横贯和团染色问题.第二章主要研究图的团横贯问题.首先我们证明了在围长为3的平面三次图上图的团横贯问题和团独立集问题是NP-完全问题并在三次图上分别给出了图的团横贯问题和团独立集问题的一个贪婪近似算法（该结果发表在《Inf.Process. Lett.》上）.其次,我们在最大度不超过4的无爪图上给出了团横贯问题的一个多项式时间算法（该部分的结果已投稿到《Inf. Process. Lett.》杂志）.最后,我们在平面图、无爪图等图类上给出了团横贯数的一些界（部分结果已被《运筹学学报》录用）.第三章主要研究了图的团染色问题.首先我们证明了非奇圈的无爪平面图是2-团可染色的并且设计了一个无爪平面图上团染色问题的一个多项式时间算法,作为一个推论我们给出了无爪平面图上团横贯数的一个紧的上界（以上结果已投稿到《Eur. J. Comb.》杂志）.其次我们证明了排除奇圈外最大度不超过7的线图是2-团可染色的并且给出了该图类的一个团染色问题的多项式时间算法.第四章主要研究了图的圈横贯问题.在本章我们指出并纠正了Brandst¨adt等人最近发表在《Theor. Comput. Sci.》上的一篇论文的错误.该文错误的证明了在最大度为4的二部图上圈横贯问题为NP-完全问题.在这里我们指出了该错误的出处及原因并给出了一个新的证明（该部分的纠错结果已投稿到《Theor. Comput. Sci.》杂志）.