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

山东大学学报（理学版） ›› 2017, Vol. 52 ›› Issue (12): 36-41.doi: 10.6040/j.issn.1671-9352.0.2016.597

• • 上一篇    下一篇

4-圈不共点的平面图的线性2-荫度

陈宏宇1,张丽2   

  1. 1. 上海应用技术大学理学院, 上海 201418;2. 上海立信会计金融学院统计与数学学院, 上海 201209
  • 收稿日期:2016-12-16 出版日期:2017-12-20 发布日期:2017-12-22
  • 作者简介:陈宏宇(1981— ),女,博士,副教授,研究方向为图论. E-mail:hongyuchen86@163.com
  • 基金资助:
    国家自然科学基金青年科学基金资助项目(11401386)

Linear 2-arboricity of planar graphs with 4-cycles have no common vertex

CHEN Hong-yu1, ZHANG Li2   

  1. 1. School of Science, Shanghai Institute of Technology, Shanghai 201418, China;
    2. School of Statistics and Mathematics, Shanghai Lixin University of Accouting and Finance, Shanghai 201209, China
  • Received:2016-12-16 Online:2017-12-20 Published:2017-12-22

PDF (PC)

810

摘要： 图G的线性2-荫度la2(G)是指可以使G分解为k个边不相交森林的最小整数k, 其中森林的每个分支是长度至多为2的路。 证明了若G是4-圈不共点的平面图,则la2(G)≤「Δ/2+5。

关键词: 平面图, 圈, 线性2-荫度

Abstract: The linear 2-arboricity la2(G)of G is the least integer k to divide G into k edge-disjoint forests, and each branch of the forests is a path with the length at most 2. We prove that if G is a planar graph with 4-cycles without common vertex, then la2(G)≤「Δ/2+5.

Key words: cycle, planar graph, linear 2-arboricity

中图分类号: 

  • O157.5
[1] HABIB M, PEROCHE B. Some problems about linear arboricity[J]. Discrete Mathematics, 1982, 41(2):219-220.
[2] CHEN B L, FU H L, HUANG K C. Decomposing graphs into forests of paths with size less than three[J]. Australas J Combin, 1991, 3:55-73.
[3] FU H L, HUANG K C. The linear 2-arboricity of complete bipartite graphs[J]. Ars Combinatoria, 1994, 38:309-318.
[4] THOMASSEN C. Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5[J]. Journal of Combinatorial Theory, 1999, 75(1):100-109.
[5] CHANG G J. Algorithmic aspects of linear k-arboricity[J]. Taiwanese Journal of Mathematics, 1999, 3(1):73-81.
[6] CHANG G J, CHEN B L, FU H L, et al. Linear k-arboricity on trees [J]. Discrete Appl Math, 2000, 103:281-287.
[7] BERMOND J C, FOUQUET J L, HABIB M, et al. On linear k-arboricity [J]. Discrete Math, 1984, 52: 123-132.
[8] JACKSON B, WORMALD N C. On the linear k-arboricity of cubic graphs[J]. Discrete Mathematics, 1996, 162(1-3):293-297.
[9] ALDRED R E L, WORMALD N C. More on the linear k-arboricity of regular graphs[J]. Australasian Journal of Combinatorics, 2014, 18:97-104.
[10] LIH K W, TONG L D, WANG W F. The linear 2-arboricity of planar graphs[J]. Graphs & Combinatorics, 2003, 19(2):241-248.
[11] 钱景,王维凡. 不含4-圈的平面图的线性2-荫度[J].浙江师范大学学报(自然科学版),2006,29(2):121-125. QIAN Jing, WANG Weifan. The linear 2-arboricity of planar graphs without 4-cycles[J]. J Zhejiang Norm Univ(Nat Sci), 2006, 29(2): 121-125.
[12] MA Qin, WU Jianliang. Planar graphs without 5-cycles or without 6-cycles [J]. Discrete Math, 2009, 309: 2998-3005.
[13] CHEN Hongyu, TAN Xiang, WU Jianliang. The linear 2-arboricity of planar graphs without adjacent short cycles [J]. Bull Korean Math Soc, 2012, 49: 145-154.
[14] 王苒群,左连翠. 不含4-圈和5-圈的平面图的线性2-荫度[J]. 山东大学学报(理学版),2012,47(6):71-75. WANG Ranqun, ZUO Liancui. The linear 2-arboricity of planar graphs without 4-cycles and 5-cycles[J]. Journal of Shandong University(Natural Science), 2012, 47(6): 71-75.
[15] 陈宏宇, 张丽. 不含弦5-圈和弦6-圈的平面图的线性2-荫度[J]. 山东大学学报(理学版), 2014, 49(6):26-30. CHEN Hongyu, ZHANG Li. The linear 2-arboricity of planar graphs without 5-, 6-cycles with chord[J]. Journal of Shandong University(Natural Science), 2014, 49(6):26-30.
[1] 张江悦,徐常青. 最大平均度不超过4的图的线性2-荫度[J]. 山东大学学报（理学版）, 2018, 53(6): 7-10.
[2] 房启明,张莉. 无4-圈和5-圈的平面图的k-frugal列表染色[J]. 山东大学学报（理学版）, 2018, 53(10): 35-41.
[3] 王晓丽,王慧娟,刘彬. 最大度为7的平面图全染色[J]. 山东大学学报（理学版）, 2017, 52(8): 100-106.
[4] 王晔,孙磊. 不含3圈和4圈的1-平面图是5-可染的[J]. 山东大学学报（理学版）, 2017, 52(4): 34-39.
[5] 何玉萍,王治文,陈祥恩. mC8的点可区别全染色[J]. 山东大学学报（理学版）, 2017, 52(10): 24-30.
[6] 谭香. 不含6-圈和相邻5-圈的平面图的全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 72-78.
[7] 白丹,左连翠. 立方圈的(d,1)-全标号[J]. 山东大学学报（理学版）, 2016, 51(4): 59-64.
[8] 朱海洋,顾 毓,吕新忠. 平面图的平方染色数的一个新上界[J]. 山东大学学报（理学版）, 2016, 51(2): 94-101.
[9] 孟宪勇, 郭建华, 苏本堂. 3-正则Halin图的完备染色[J]. 山东大学学报（理学版）, 2015, 50(12): 127-129.
[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   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发