论文部分内容阅读
图的染色问题是图论研究中的重要问题之一，有重要的理论价值和应用背景。2004年，Fertin等提出了星染色的概念。2006年，刘信生等提出了星边染色的概念，若图G的一个正常边染色满足G中没有长为4的路是2-边染色的，则称此染色是G的一个星边染色，使得G有星边染色的最小颜色数称为星边色数，记作Xs(G)。图的星边染色不仅对研究星染色有重要的意义，而且星边染色和星边色数与无圈边染色和无圈边色数a(G)(Grünbaum，1973)以及强边染色和强边色数Sx(G)(Erdos，1986)有密切关系。到目前为止，关于星边染色还有很多问题有待解决。
本文研究了一些特殊图类的星边染色，主要有以下结果：
1．研究了若干笛卡尔积图的星边染色，并分别得到了Pm□Pn、Pm□Cn、Pm□Sn、Pm□Fn、Pm□Wn的星边色数；
2．研究了广义Petersen图的星边染色，进而得到了P(n，2)的星边色数；
3．研究了路与路联图的星边染色，进而得到了Pm∨Pn的星边色数。