华东师范大学学报（自然科学版） >

2016 , Vol. 2016 >Issue 2: 51 - 55

DOI: https://doi.org/2016.02.007

数学

非负特征图的列表不完全染色的研究(英)

  • 许洋
展开
  • 青岛农业大学~~理学与信息科学学院, 山东~青岛 266109)

收稿日期: 2015-04-01

  网络出版日期: 2016-07-25

收起

List improper coloring of graphs of nonnegative characteristic

  • XU Yang
Expand

Received date: 2015-04-01

  Online published: 2016-07-25

Fold

摘要

对每一个顶点~$v\in V(G)$, 若任意给定~$k$~种颜色的列表,$G$~都存在一个~$L$-染色,使得~$G$~的每个顶点至多有~$d$~个邻接点与其染相同的颜色,
则称图~$G$~为~$(k,d)^*$-可选的. 设~$G$~为可以嵌入到非负特征曲面的图.本文证明了若图~$G$~为~2-连通的, 且不包含~5-圈、邻接的~3-面和邻接的~4-面时, $G$~是~$(3,1)^*$-可选的.

关键词： 列表不完全染色; 特征; 圈;欧拉公式

本文引用格式

许洋 . 非负特征图的列表不完全染色的研究(英)[J]. 华东师范大学学报（自然科学版）, 2016 , 2016(2) : 51 -55 . DOI: 2016.02.007

Abstract

A graph G is called (k,d)^*-choosable if, for every list assignment L with |L(v)|=k for all v\in V(G), there is anL$-coloring of G such that every vertex has at most d neighbors receiving the same color as itself. Let G be a graph embedded in a surface of nonnegative characteristic. In this paper, we prove that if G is a 2-connected graph, which contains no 5-cycles, adjacent 3-faces and adjacent 4-faces, then G is (3,1)^*-choosable

Key words： list improper coloring;characteristic; cycle;Euler's formula

参考文献

[1]PETAKOS K, TSAPELAS T. Reliability analysis for systems in a random enviroment [J]. Journal of Applied Probability, 1997, 34: 1021-1031.
[2]LI Z H, ZHAO P. Reliability analysis on the delta -shock model of complex systems [J]. IEEE Transactions On Reliability, 2007, 56(2):340-348.
[3]CHANG G J, CUI L R, HWANG F K. Reliabilities of Consecutive-k-out-of-n Systems [M]. Dordrecht, Netherlands:Kluwer Academic Publishers, 2000.
[4]CHENG K, ZHANG Y L. Analysis for a consecutive-k-out-of-n:F repairable system with priorityin repair [J]. International Journal of Systems Science, 2001, 32(5): 591-598.
[5]CUI L R. The IFR property for consecutive-k-out-of-n:F systems [J]. Statist Probab Letters, 2002, 59(4): 405-414.
[6]CUI L R, HAWKES A G. A note on the proof for the optimal consecutive-k-out-of-n: G line for n\leq2k [J]. Statis Plann Inference, 2008, 138(5): 1516-1520.
[7]GERA A E. A consecutive-k-out-of-n: G system with dependence elements-a matrix formulation and solution [J]. Reliab Eng Syst Saf, 2000, 68(1): 61-67.
[8]GUAN J C, WU Y Q. Repairable consecutive-k-out-of-n:F systems with fuzzy state [J]. Fuzzy Sets and Systems, 2006, 157(1): 121-142.
[9]JALALI A, HAWKES A G, CUI L R, et al. The optimal consecutive-k-out-of-n: G line for n\leq2k [J]. Statist Plann Inference, 2005, 128: 281-287.
[10]LAM Y, ZHANG Y L. Repairable consecutive-k-out-of-n: G systems [J]. Chinese J Trans, 2000, 4(3): 19-32.
[11]LIANG X L, LI Z H. Reliability analysis for consecutive-k-out-of-n: G repairable system [C]//Proceedings of the 4th International Conference on Quality and Reliability (ICQR).

2005: 855-869.
[12]康庆德. 组合学笔记~[M]. 北京: 科学出版社, 2009.
Options
文章导航

/

〈 〉