您的位置:山东大学 -> 科技期刊社 -> 《山东大学学报(理学版)》

《山东大学学报(理学版)》 ›› 2018, Vol. 53 ›› Issue (12): 17-22.doi: 10.6040/j.issn.1671-9352.0.2017.539

• • 上一篇    下一篇

可嵌入到欧拉示性数非负的曲面图的线性荫度

陈洪玲,王慧娟*,高红伟   

  1. 青岛大学数学与统计学院, 山东 青岛 266071
  • 出版日期:2018-12-20 发布日期:2018-12-18
  • 作者简介:陈洪玲(1993— ),女,硕士研究生,研究方向为博弈论及其应用. E-mail:chlqdu@163.com*通信作者简介:王慧娟(1985— ),女,博士,副教授,研究方向为图论与组合最优化. E-mail:sduwhj@163.com
  • 基金资助:
    国家自然科学基金资助项目(71571108,11501316);国家自然科学基金国际(地区)合作交流项目(71611530712,61661136002)

Linear arboricity of graphs embedded in a surface of non-negative Euler characteristic

CHEN Hong-ling, WANG Hui-juan*, GAO Hong-wei   

  1. School of Mathematics and Statistics, Qingdao University, Qingdao 266071, Shandong, China
  • Online:2018-12-20 Published:2018-12-18

摘要: 图G的线性荫度是一种非正常的边染色,即它的边集合E(G)可以分割成线性森林的最小数量,用la(G)表示。主要研究最大度Δ(G)≥7且可嵌入到欧拉示性数非负曲面图G上的线性荫度,证明了如果图G中不含相邻的含弦6-圈,则图G的线性荫度为「Δ/2。

关键词: 欧拉示性数, 线性森林,

Abstract: The linear arboricity of graph G, denoted by la(G), is the minimum number of linear forest required to partition the edge set E(G), which is an improper edge coloring. The linear arboricity of graph which can be embedded in a surface of non-negative Euler characteristic with maximum Δ(G)≥7 is mainly studied. If there is no adjacent chordal 6-cycle, then the arboricity of graph G is「Δ/2.

Key words: Euler characteristic, linear forest, cycle

中图分类号: 

  • O157.5
[1] FRANK H. Covering and packing in graphs, I.[J]. Annals of the New York Academy of Sciences, 2010, 175(1):198-205.
[2] AKIYAMA J, EXOO G, HARARY F. Covering and packing in graphs III: cyclic and acyclic invariants[J]. Mathematica Slovaca, 1980, 30(4):405-417.
[3] WU J L, LIU G, WU Y W. The linear arboricity of composition graphs[J]. Journal of Systems Science & Complexity, 2002, 15(4):38-41.
[4] WU Jianling. The linear arboricity of Series-Parallel graphs[J]. Graphs & Combinatorics, 2000, 16(3):367-372.
[5] JIN A, EXOO G, HARARY F. Covering and packing in graphs IV: linear arboricity[J]. Networks, 2010, 11(1):69-72.
[6] ENMOTO H, PEROCHE B. The linear arboricity of some regular graphs[J]. Journal of Graph Theory, 1984, 8(2):309-324.
[7] GULDAN F. The linear arboricity of 10 regular graph[J]. Mathematical Institute of the Slovak Academy of Sciences, 1986, 36(3):225-228.
[8] WU Jianliang. On the linear arboricity of planar graphs[J]. Journal of Graph Theory, 1999, 31(2):129-134.
[9] WU Jianliang, WU Yuwen. The linear arboricity of planar graphs of maximum degree seven are four[J]. Journal of Graph Theory, 2008, 58(3):210-220.
[10] CYGAN M, HOU J, KOWALIK L, et al. A planar linear arboricity conjecture[J]. Journal of Graph Theory, 2012, 69(4):403-425.
[11] WANG Huijuan, WU Lidong, WU Weili, et al. Minimum number of disjoint linear forests covering a planar graph[J]. Journal of Combinatorial Optimization, 2014, 28(1):274-287.
[12] ALON N. The linear arboricity of graphs[J]. Israel Journal of Mathematics, 1988, 62(3):311-325.
[13] WU Jianliang, HOU Jianfeng, SUN Xiangyong. A note on the linear arboricity of planar graphs without 4-cycles[J]. The Eighth International Symposium on Operations Research and Its Applications, 2009, 09:174-178.
[1] 张江悦,徐常青. 最大平均度不超过4的图的线性2-荫度[J]. 山东大学学报(理学版), 2018, 53(6): 7-10.
[2] 李强,马丽丽,王晓燕,吕莉娇. Hom-Jordan李代数的交换扩张[J]. 《山东大学学报(理学版)》, 2018, 53(12): 4-8.
[3] 刘佳,孙磊. 不含4-圈或弦6-圈的平面图是(3,0,0)-可染的[J]. 《山东大学学报(理学版)》, 2018, 53(12): 31-40.
[4] 房启明,张莉. 无4-圈和5-圈的平面图的k-frugal列表染色[J]. 山东大学学报(理学版), 2018, 53(10): 35-41.
[5] 王晓丽,王慧娟,刘彬. 最大度为7的平面图全染色[J]. 山东大学学报(理学版), 2017, 52(8): 100-106.
[6] 陈宏宇,张丽. 4-圈不共点的平面图的线性2-荫度[J]. 山东大学学报(理学版), 2017, 52(12): 36-41.
[7] 何玉萍,王治文,陈祥恩. mC8的点可区别全染色[J]. 山东大学学报(理学版), 2017, 52(10): 24-30.
[8] 谭香. 不含6-圈和相邻5-圈的平面图的全染色[J]. 山东大学学报(理学版), 2016, 51(4): 72-78.
[9] 白丹,左连翠. 立方圈的(d,1)-全标号[J]. 山东大学学报(理学版), 2016, 51(4): 59-64.
[10] 薛丽霞, 李志慧, 谢佳丽. 对3条超边的超圈存取结构最优信息率的一点注记[J]. 山东大学学报(理学版), 2015, 50(11): 60-66.
[11] 王珊珊, 齐恩凤. k-连通图中最长圈上可收缩边的数目[J]. 山东大学学报(理学版), 2015, 50(10): 27-31.
[12] 孟献青. 一类平面图的强边染色[J]. 山东大学学报(理学版), 2015, 50(08): 10-13.
[13] 张绍华, 颜谨, 李硕. 图中相互独立的4-圈和8-圈[J]. 山东大学学报(理学版), 2015, 50(02): 1-4.
[14] 杨陈, 马海成. 两类特殊三圈图的正负惯性指数和零度[J]. 山东大学学报(理学版), 2015, 50(02): 32-37.
[15] 马刚. 围长不小于11且最大度为3的平面图的#br# 无圈列表边染色[J]. 山东大学学报(理学版), 2014, 49(2): 18-23.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 杨军. 金属基纳米材料表征和纳米结构调控[J]. 山东大学学报(理学版), 2013, 48(1): 1 -22 .
[2] 赵君1,赵晶2,樊廷俊1*,袁文鹏1,3,张铮1,丛日山1. 水溶性海星皂苷的分离纯化及其抗肿瘤活性研究[J]. J4, 2013, 48(1): 30 -35 .
[3] 孙小婷1,靳岚2*. DOSY在寡糖混合物分析中的应用[J]. J4, 2013, 48(1): 43 -45 .
[4] 杨伦,徐正刚,王慧*,陈其美,陈伟,胡艳霞,石元,祝洪磊,曾勇庆*. RNA干扰沉默PID1基因在C2C12细胞中表达的研究[J]. J4, 2013, 48(1): 36 -42 .
[5] 杨莹,江龙*,索新丽. 容度空间上保费泛函的Choquet积分表示及相关性质[J]. J4, 2013, 48(1): 78 -82 .
[6] 李永明1, 丁立旺2. PA误差下半参数回归模型估计的r-阶矩相合[J]. J4, 2013, 48(1): 83 -88 .
[7] 杨永伟1,2,贺鹏飞2,李毅君2,3. BL-代数的严格滤子[J]. 山东大学学报(理学版), 2014, 49(03): 63 -67 .
[8] 赵同欣1,刘林德1*,张莉1,潘成臣2,贾兴军1. 紫藤传粉昆虫与花粉多型性研究[J]. 山东大学学报(理学版), 2014, 49(03): 1 -5 .
[9] 汤晓宏1,胡文效2*,魏彦锋2,蒋锡龙2,张晶莹2,. 葡萄酒野生酿酒酵母的筛选及其生物特性的研究[J]. 山东大学学报(理学版), 2014, 49(03): 12 -17 .
[10] 王碧玉,曹小红*. 算子矩阵的Browder定理的摄动[J]. 山东大学学报(理学版), 2014, 49(03): 90 -95 .