共查询到19条相似文献,搜索用时 93 毫秒
1.
2.
3.
4.
路与完全图的笛卡尔积图和广义图K(n,m)的关联色数 总被引:4,自引:0,他引:4
Richrd A.Brualdi和J.Quinn Massey在[1]中引入了图的关联着色概念,并且提出了关联着色猜想,即每一个图G都可以用△(G)+2种色正常关联着色.B.Guiduli[2]说明关联着色的概念是I.Algor和N.Alon[3]提出的有向星荫度的一个特殊情况,并证实[1]的关联着色猜想是错的,给出图G的关联色数的一个新的上界是△(G)+O(Log(△G)).[4]确定了某些特殊图类的关联色数.本文给出了路和完全图的笛卡尔积图的关联色数,而且利用此结果又确定了完全图Kn的广义图K(n,m)的关联色数. 相似文献
5.
6.
本文给出了路与路,路与圈的卡氏乘积图的关联着色数的完整刻画.对于圈与圈的卡氏乘积图的情形,也给出了其关联着色数的上界为乘积图的最大度加三,并且又给出了几类其关联着色数小于其最大度加三的圈与圈的卡氏乘积图类. 相似文献
7.
简要介绍了图的关联着色问题的起源、发展情况及目前已有的结论,对一类特殊的图——极大外平面图(△≠6),给出了其关联色数. 相似文献
8.
图的关联着色是从关联集到颜色集的一个映射,使得关联集中任何两个相邻的关联都具有不同的像.确定了Meredith图的关联色数,证明了对任意系列平行图都存在一个(Δ 2,2)-关联着色. 相似文献
9.
《数学的实践与认识》2013,(23)
图G的一个正常边染色被称作邻点可区别无圈边染色,如果G中无二色圈,且相邻点关联边的色集合不同.图G的邻点可区别无圈边色数记为χ′_(aa)(G),即图G的一个邻点可区别无圈边染色所用的最少颜色数.通过构造具体染色的方法,给出了一些k-方图的邻点可区别无圈边色数. 相似文献
10.
11.
通过引进Mycielski图点集的一类特殊划分,利用该划分在Mycielski图循环着色中的特点改进了如下猜想:完全图的Mycielski图的循环色数等于它的点色数. 相似文献
12.
Mycielski图的循环色数 总被引:1,自引:0,他引:1
通过引入一类点集划分的概念,研究了Mylielski图循环染色的性质,证明了当完全图的点数足够大时,它的Mycielski图的循环色数与其点色数相等. 相似文献
13.
On adjacent-vertex-distinguishing total coloring of graphs 总被引:40,自引:0,他引:40
In this paper, we present a new concept of the adjacent-vertex-distinguishing total coloring of graphs (briefly, AVDTC of graphs) and, meanwhile, have obtained the adjacent-vertex-distinguishing total chromatic number of some graphs such as cycle, complete graph, complete bipartite graph, fan, wheel and tree. 相似文献
14.
Incidence coloring of a graph G is a mapping from the set of incidences to a color-set C such that adjacent incidences of G are assigned distinct colors. Since 1993, numerous fruitful results as regards incidence coloring have been proved. However, some of them are incorrect. We remedy the error of the proof in [R.A. Brualdi, J.J.Q. Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993) 51-58] concerning complete bipartite graphs. Also, we give an example to show that an outerplanar graph with Δ=4 is not 5-incidence colorable, which contradicts [S.D. Wang, D.L. Chen, S.C. Pang, The incidence coloring number of Halin graphs and outerplanar graphs, Discrete Math. 256 (2002) 397-405], and prove that the incidence chromatic number of the outerplanar graph with Δ≥7 is Δ+1. Moreover, we prove that the incidence chromatic number of the cubic Halin graph is 5. Finally, to improve the lower bound of the incidence chromatic number, we give some sufficient conditions for graphs that cannot be (Δ+1)-incidence colorable. 相似文献
15.
Jiaojiao Wu 《Discrete Mathematics》2009,309(12):3866-3870
This paper proves that if G is a cubic graph which has a Hamiltonian path or G is a bridgeless cubic graph of large girth, then its incidence coloring number is at most 5. By relating the incidence coloring number of a graph G to the chromatic number of G2, we present simple proofs of some known results, and characterize regular graphs G whose incidence coloring number equals Δ(G)+1. 相似文献
16.
17.
18.
本文研究了积图的点可区别均匀边染色问题.利用构造法得到了积图G×G的点可区别均匀边染色的一个结论,并且获得了等阶的完全图与完全图、星与星、轮与轮的积图的点可区别均匀边色数,验证了它们满足点可区别均匀边染色猜想(VDEECC). 相似文献
19.
《Discrete Mathematics》2023,346(1):113162
The graph coloring game is a two-player game in which the two players properly color an uncolored vertex of G alternately. The first player wins the game if all vertices of G are colored, and the second wins otherwise. The game chromatic number of a graph G is the minimum integer k such that the first player has a winning strategy for the graph coloring game on G with k colors. There is a lot of literature on the game chromatic number of graph products, e.g., the Cartesian product and the lexicographic product. In this paper, we investigate the game chromatic number of the strong product of graphs, which is one of major graph products. In particular, we completely determine the game chromatic number of the strong product of a double star and a complete graph. Moreover, we estimate the game chromatic number of some King's graphs, which are the strong products of two paths. 相似文献