圈与路联图点可区别Ⅰ-全染色和点可区别Ⅵ-全染色

删除或更新信息，请邮件至freekaoyan#163.com(#换成@)

本站小编 Free考研考试/2024-01-16

-->

苗婷婷,王治文,陈祥恩.圈与路联图点可区别Ⅰ-全染色和点可区别Ⅵ-全染色[J].,2017,57(4):430-435

圈与路联图点可区别Ⅰ-全染色和点可区别Ⅵ-全染色

Vertex-distinguishing Ⅰ-total colorings and vertex-distinguishing Ⅵ-total colorings of join-graph of cycle and path

DOI：10.7511/dllgxb201704015

中文关键词:Ⅰ-全染色点可区别Ⅰ-全染色点可区别Ⅰ-全色数圈与路的联

英文关键词:Ⅰ-total coloring vertex-distinguishing Ⅰ-total coloring vertex-distinguishing Ⅰ-total chromatic number join of cycle and path

基金项目:国家自然科学基金资助项目(61163037611630541126104661363060)；宁夏回族自治区****资助项目.

作者	单位
苗婷婷,王治文,陈祥恩

摘要点击次数:1120

全文下载次数:870

中文摘要:

一个图 G 的Ⅰ-全染色是指若干种颜色对图 G 的全体顶点及边的一个分配使得任意两个相邻点及任意两条相邻边被分配到不同颜色．图 G 的Ⅵ-全染色是指若干种颜色对图 G 的全体顶点及边的一个分配使得任意两条相邻边被分配到不同颜色．对图 G 的一个Ⅰ(Ⅵ)-全染色及图 G 的任意一个顶点 x，用C(x)表示顶点x的颜色及x 的关联边的颜色构成的集合(非多重集)．如果 f 是图 G 的使用 k 种颜色的一个Ⅰ(Ⅵ)-全染色，并且 u，v∈V(G)，u≠v，有C(u)≠C(v)，则称f为图G的k -点可区别Ⅰ(Ⅵ)-全染色，或 k -VDITC(VDVITC)．图 G 的点可区别Ⅰ(Ⅵ)-全染色所需最少颜色数目，称为图 G 的点可区别Ⅰ(Ⅵ)-全色数．利用组合分析法及构造具体染色的方法，讨论了圈与路的联图 C m∨P n 的点可区别Ⅰ(Ⅵ)-全染色问题，确定了这类图的点可区别Ⅰ(Ⅵ)-全色数，同时说明了VDITC猜想和VDVITC猜想对于这类图是成立的．

英文摘要:

Ⅰ-total coloring of a graph G is an assignment of several colors to the vertices and edges of graph G such that any two adjacent vertices receive different colors and any two adjacent edges receive different colors. Ⅵ-total coloring of a graph G is an assignment of several colors to the vertices and edges of graph G such that any two adjacent edges receive different colors. For Ⅰ(Ⅵ)-total coloring of graph G and a vertex x of graph G , C(x) is used to denote the set (not multiset) composed of color of x and colors of the edges incident with x . Let f be Ⅰ(Ⅵ)-total coloring of a graph G using k colors and C(u)≠C(v) for any two different vertices u and v of graph G , then f is called a k -vertex-distinguishing Ⅰ(Ⅵ)-total coloring of graph G , or k -VDITC (VDVITC) of graph G for short. The minimum number of colors required in a VDITC (VDVITC) is the vertex-distinguishing Ⅰ(Ⅵ)-total chromatic number. The problems of vertex-distinguishing Ⅰ(Ⅵ)-total colorings of the join-graph C m∨P n of cycle and path are discussed by the method of combinatorial analysis and constructing concrete coloring. Meanwhile, vertex-distinguishing Ⅰ(Ⅵ)-total chromatic numbers of graph C m∨P n are determined. The results illustrate that the VDITC conjecture and VDVITC conjecture are valid for graph C m∨P n .

查看全文查看/发表评论下载PDF阅读器

关闭

圈与路联图点可区别Ⅰ-全染色和点可区别Ⅵ-全染色

本站小编 Free考研考试/2024-01-16

相关话题/

领限时大额优惠券,享本站正版考研考试资料!