不含三角形图的正常染色路和正常染色圈  

The properly colored paths and cycles for the triangle-free graphs

作　　者：丁录顺[1] 王光辉[1] 颜谨[1] 

机构地区：[1]山东大学数学学院,济南250100

出　　处：《运筹学学报》2014年第3期116-120,共5页Operations Research Transactions

基　　金：国家自然科学基金(No.11271230);山东省自然科学基金(No.ZR2012AM023)

摘　　要：图G为边染色图,对G中的任一顶点v,定义v的色度d^c(v):G中与顶点v相关联的边中不同染色的数目.用δ~c(G)表示图G的最小色度,即δ~c(G)=min{d^c(v):v∈G}.若图G为不含三角形的边染色图,且δ~c(G)≥2,则G含长为4d-2的正常染色路或长至少为2d-2的正常染色圈.Let G be an edge colored graph, v be a vertex in G. de（v） denotes the color degree of a vertex v, i.e. the number of edges with distinct colors incident to v. At the same time, δc（G） denotes the minimum color degree of G, i.e. δc（G） = min{dC（v） ： v C G}. Let G be an edge colored triangle-free graph such that δc（G） ≥2. We prove that G contains a properly colored path of length 4d - 2 or a properly colored cycle of length at least 2d- 2.

关 键 词：图 正常染色路 正常染色圈 

分 类 号：O157.5[理学—数学]