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

《山东大学学报(理学版)》 ›› 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)

652

摘要： 如果图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] 雷飞,文飞,李泽鹏,李沐春. 图的字典积的点可约边染色[J]. 《山东大学学报(理学版)》, 2024, 59(10): 107-114.
[2] 方子强,李龙捷,任海珍. 积运算符号图的谱[J]. 《山东大学学报(理学版)》, 2024, 59(10): 101-106.
[3] 梅银珍,符惠芬. 四类运算图的Sombor指数[J]. 《山东大学学报(理学版)》, 2024, 59(6): 56-63.
[4] 王丽,李敬文,杨文珠,裴华艳. 单圈图的邻点可约全标号[J]. 《山东大学学报(理学版)》, 2024, 59(6): 44-55.
[5] 胡开洋,黄明芳,马宝林. 完全二部图K12, n(12≤n≤88)的点可区别E-全染色[J]. 《山东大学学报(理学版)》, 2024, 59(6): 36-43, 70.
[6] 王勇军,陈祥恩. 完全三部图的点被多重集可区别的一般全染色[J]. 《山东大学学报(理学版)》, 2024, 59(6): 29-35.
[7] 陈宏宇. 树宽较小的图的线性荫度[J]. 《山东大学学报(理学版)》, 2024, 59(6): 25-28, 35.
[8] 马海成,攸晓杰. k-桥图匹配最大根的极值[J]. 《山东大学学报(理学版)》, 2024, 59(6): 19-24.
[9] 薛睿滢,魏宗田,翟美娟. 图的限制性燃烧连通度[J]. 《山东大学学报(理学版)》, 2024, 59(2): 91-99, 109.
[10] 朱莉,李鹏,王爱法. 单位区间图的半配对k-不相交路覆盖研究[J]. 《山东大学学报(理学版)》, 2024, 59(2): 80-90.
[11] 苏亚男,仝春灵,李勇,苏森原. 广义Petersen图P（n, k）的等全着色[J]. 《山东大学学报(理学版)》, 2024, 59(2): 71-79.
[12] 梁超凡,刘奋进,李玉超,柳顺义. 奇异同谱图的构造[J]. 《山东大学学报(理学版)》, 2024, 59(2): 65-70.
[13] 史雅馨,刘凤霞,蔡华. Wn□Pm的r-hued染色[J]. 《山东大学学报(理学版)》, 2024, 59(2): 59-64.
[14] 刘欢,强会英,王洪申,白羽. 树图的2-距离和可区别染色[J]. 《山东大学学报(理学版)》, 2024, 59(2): 47-52, 58.
[15] 曹静,陈祥恩. 轮与扇的点被多重集可区别的E-全染色[J]. 《山东大学学报(理学版)》, 2024, 59(2): 38-46.
Viewed
Full text


Abstract

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