JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2019, Vol. 54 ›› Issue (6): 59-70.doi: 10.6040/j.issn.1671-9352.0.2017.577

Previous Articles    

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

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

CLC Number: 

  • 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] . Vertex-distinguishing E-total coloring of complete bipartite graph K10,n with 10≤n≤90 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(12): 23-30.
[2] ZHANG You, HUANG Li-na, LI Mu-chun. Vertex distinguishing edge coloring of a hexagonal system [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(12): 41-47.
[3] CHEN Hong-ling, WANG Hui-juan, GAO Hong-wei. Linear arboricity of graphs embedded in a surface of non-negative Euler characteristic [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(12): 17-22.
[4] LIU Jia, SUN Lei. Planar graphs without 4-cycle or chordal-6-cycle are(3,0,0)-colorable [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(12): 31-40.
[5] LI Mei-lian, DENG Qing-ying. Maple calculation of the transition polynomial of plane graph [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(10): 27-34.
[6] . Vertex-distinguishing IE-total coloring and general-total coloring of K1,3,p and K1,4,p [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(8): 53-60.
[7] LIU Xiao-hua, MA Hai-cheng. Order of matching energy and Hosoya index of Q-shape graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(8): 61-65.
[8] CHEN Hong-yu, ZHANG Li. Linear 2-arboricity of planar graphs with 4-cycles have no common vertex [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(12): 36-41.
[9] HE Yu-ping, WANG Zhi-wen, CHEN Xiang-en. Vertex-distinguishing total coloring of mC8 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(10): 24-30.
[10] LI Ting-ting, LAO Hui-xue. On the mean value of a hybrid arithmetic function [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(8): 70-74.
[11] WANG Xiao-li, WANG Hui-juan, LIU Bin. Total coloring of planar graphs with maximum degree seven [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(8): 100-106.
[12] CHEN Xiang-en, MIAO Ting-ting, WANG Zhi-wen. Vertex-distinguishing I-total colorings of the join of two paths [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(4): 30-33.
[13] MA Hai-cheng, LI Sheng-gang. The digraphs representation of finite topologies [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(4): 100-104.
[14] WANG Ye, SUN Lei. Every 1-planar graph without cycles of length 3 or 4 is 5-colorable [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(4): 34-39.
[15] ZHU Xiao-ying, PANG Shi-you. On the maximal eccentric distance sum of tree with given domination number [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(2): 30-36.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!