您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2019, Vol. 54 ›› Issue (6): 59-70.doi: 10.6040/j.issn.1671-9352.0.2017.577

• • 上一篇    

广义θ-链的区间边着色

陈勋1,黄琼湘1*,陈琳2   

  1. 1. 新疆大学数学与系统科学学院, 新疆 乌鲁木齐 830046;2. 新疆医科大学医学工程技术学院, 新疆 乌鲁木齐 830011
  • 发布日期:2019-06-05
  • 作者简介:陈勋(1993— ), 男, 硕士研究生, 研究方向为图论及其应用. E-mail:chenxjq@foxmail.com*通信作者简介:黄琼湘(1958—), 男, 博士, 教授, 博士生导师, 研究方向为代数图论. E-mail:huangqx@xju.edu.cn
  • 基金资助:
    国家自然科学基金资助项目(11671344)

Interval edge-coloring of the generalized θ-chain

CHEN Xun1, HUANG Qiong-xiang1*, CHEN Lin2   

  1. 1. College of Mathematics and System Science, Xinjiang University, Urumqi 830046, Xinjiang, China;
    2. College of Medical Engineering and Technology, Xinjiang Medical University, Urumqi 830011, Xinjiang, China
  • Published:2019-06-05

PDF (PC)

455

摘要： 如果图G的一个边着色用了1,2,…,t中的所有颜色,并且关联于G的同一个顶点的边上的颜色各不相同,且这些颜色构成了一个连续的整数区间,则称这个边着色是G的区间t-着色。如果对某个正整数t,G有一个区间t-着色,则称G是可区间着色的。所有可区间着色的图构成的集合记作N。图G的亏度def(G)是粘在G的顶点上使它可区间着色的悬挂边的最小数目,显然,G∈N当且仅当def(G)=0。广义θ-链是把路P=［v0,v1,…,vk］(k≥1)的每一条边vi-1vi(i=1,2,…,k),用mi≥2条两两内部不交的(vi-1,vi)-路替换掉而得到的简单图,记作θm1,m2,…,mk。把广义θ-图亏度的结论进行推广,确定了θm1,m2,…,mk的亏度。

关键词: 区间边着色, 亏度, 广义θ-图, 广义θ-链

Abstract: An edge-coloring of a graph G with colors 1,2,…,t is an interval t-coloring if all colors are used, and the colors of edges incident to each vertex of G are distinct and form a continuous interval of integer. A graph G is interval colorable if it has an interval t-coloring for some positive integer t. The set of all interval colorable graphs is denoted by N. The deficiency def(G)of a graph G is the minimum number of pendant edges whose attachment to G makes it interval colorable. Obviously, G∈N if and only if def(G)=0. A generalized θ-chain, denoted by θm1,m2,…,mk, is a simple graph obtained by substituting each edge vi-1vi of the path P=［v0,v1,…,vk］(k≥1)for mi≥2 pairwise internally disjoint(vi-1,vi)-paths, where i=1,2,…,k. In this paper, the conclusions of deficiency of generalized θ-graph are generalized, and the deficiency of the generalized θ-chain θm1,m2,…,mk is determined.

Key words: interval edge-coloring, deficiency, generalized θ-graph, generalized θ-chain

中图分类号: 

  • O157.5
[1] ASRATIAN A S, KAMALIAN R R. Interval colorings of edges of a multigraph[J]. Applied Mathematics, 1987, 5:25-34.
[2] ASRATIAN A S, KAMALIAN R R. Investigation on interval edge-colorings of graphs[J]. Journal of Combinatorial Theory, Series B, 1994, 62(1):34-43.
[3] KAMALIAN R R. Interval edge colorings of graphs[D]. Novosibirsk:[s.l.] , 1990.
[4] GIARO K, KUBALE M, MAAFIEJSKI M. Consecutive colorings of the edges of general graphs[J]. Discrete Mathematics, 2001, 236(1):131-143.
[5] AXENOVICH M A. On interval colorings of planar graphs[J]. Congressus Numerantium, 2002, 159:77-94.
[6] KAMALIAN R R, PETROSYAN P A. A note on interval edge-colorings of graphs[J]. Mathematical Problems of Computer Science, 2012, 36:13-16.
[7] KAMALIAN R R. Interval colorings of complete bipartite graphs and trees[J]. Undergraduate Topics in Computer Science, 2013:183-231.
[8] 陶艳亮. 图的区间边着色的收缩图方法[D]. 乌鲁木齐:新疆大学, 2017. TAO Yanliang. Contraction graph method for the interval edge-coloring of graphs[D]. Urumqi: Xinjiang University, 2017.
[9] PETROSYAN P A. Interval edge-colorings of complete graphs and n-dimensional cubes[J]. Discrete Mathematics, 2010, 310:1580-1587.
[10] PETROSYAN P A, KHACHATRIAN H H, TANANYAN H G. Interval edge-colorings of Cartesian products of graphs I[J]. Discussiones Mathematicae Graph Theory, 2013, 33:613-632.
[11] PETROSYAN P A. Interval edge-colorings of Möbius ladders[J]. Proceedings of the CSIT Conference, 2005: 146-149.
[12] GIARO K, KUBALE M, MAAFIEJSKI M. On the deficiency of bipartite graphs[J]. Discrete Applied Mathematic, 1999, 94:193-203.
[13] 张维娟.单圈图和双圈图的连续边着色[J].新疆大学学报(自然科学版), 2006, 23(1):20-24. ZHANG Weijuan. Consecutive colorings of the edges of unicyclic and bicyclic graphs[J]. Journal of Xinjiang University, 2006, 23(1):20-24.
[14] BOROWIECKA-OLSZEWSKA M, DRGAS-BURCHARDT E. The deficiency of all generalized Hertz graphs and minimal consecutively non-colourable graphs in this class[J]. Discrete Mathematics, 2016, 339(7):1892-1908.
[15] BOROWIECKA-OLSZEWSKA M, DRGAS-BURCHARDT E, HAŁUSZCZAK M. On the structure and deficiency of k-trees with bounded degree[J]. Discrete Applied Mathematic, 2016, 201:24-37.
[16] PETROSYAN P A, KHACHATRIAN H H. Further results on the deficiency of graphs[J]. Discrete Applied Mathematics, 2017, 226:117-126.
[17] FENG Yongde, HUANG Qiongxiang. Consecutive edge-coloring of the generalized θ-graph[J]. Discrete Applied Mathematics, 2007, 155(17):2321-2327.
[1] 包丽娅,陈祥恩,王治文. 完全二部图K10,n(10≤n≤90)的点可区别E-全染色[J]. 《山东大学学报(理学版)》, 2018, 53(12): 23-30.
[2] 张友,黄丽娜,李沐春. 一类六角系统的点可区别边染色[J]. 《山东大学学报(理学版)》, 2018, 53(12): 41-47.
[3] 陈洪玲,王慧娟,高红伟. 可嵌入到欧拉示性数非负的曲面图的线性荫度[J]. 《山东大学学报(理学版)》, 2018, 53(12): 17-22.
[4] 刘佳,孙磊. 不含4-圈或弦6-圈的平面图是(3,0,0)-可染的[J]. 《山东大学学报(理学版)》, 2018, 53(12): 31-40.
[5] 李美莲,邓青英. 平图的transition多项式的Maple计算[J]. 山东大学学报（理学版）, 2018, 53(10): 27-34.
[6] 寇艳芳,陈祥恩,王治文. K1,3,p和 K1,4,p的点可区别的IE-全染色及一般全染色[J]. 山东大学学报（理学版）, 2018, 53(8): 53-60.
[7] 刘小花,马海成. Q形图的匹配能序及Hosoya指标排序[J]. 山东大学学报（理学版）, 2018, 53(8): 61-65.
[8] 陈宏宇,张丽. 4-圈不共点的平面图的线性2-荫度[J]. 山东大学学报（理学版）, 2017, 52(12): 36-41.
[9] 何玉萍,王治文,陈祥恩. mC8的点可区别全染色[J]. 山东大学学报（理学版）, 2017, 52(10): 24-30.
[10] 李亭亭,劳会学. 一类混合型数论函数的均值估计[J]. 山东大学学报（理学版）, 2017, 52(8): 70-74.
[11] 王晓丽,王慧娟,刘彬. 最大度为7的平面图全染色[J]. 山东大学学报（理学版）, 2017, 52(8): 100-106.
[12] 陈祥恩,苗婷婷,王治文. 两条路的联图的点可区别I-全染色[J]. 山东大学学报（理学版）, 2017, 52(4): 30-33.
[13] 马海成,李生刚. 有限拓扑的有向图表示[J]. 山东大学学报（理学版）, 2017, 52(4): 100-104.
[14] 王晔,孙磊. 不含3圈和4圈的1-平面图是5-可染的[J]. 山东大学学报（理学版）, 2017, 52(4): 34-39.
[15] 朱晓颖,逄世友. 控制数给定的树的最大离心距离和[J]. 山东大学学报（理学版）, 2017, 52(2): 30-36.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发