Color degree and heterochromatic cycles in edge-colored graphs

被引：28
作者：
Li, Hao [1 ,2 ]
Wang, Guanghui [3 ]
机构：
[1] Univ Paris 11, CNRS, UMR 8623, Lab Rech Informat, F-91405 Orsay, France
[2] Lanzhou Univ, Sch Math & Stat, Lanzhou 730000, Peoples R China
[3] Shandong Univ, Sch Math, Jinan 250100, Shandong, Peoples R China
来源：
EUROPEAN JOURNAL OF COMBINATORICS | 2012年 / 33卷 / 08期
关键词：
RAINBOW SUBGRAPHS; MATCHINGS;
D O I：
10.1016/j.ejc.2012.06.005
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Given a graph G and an edge-coloring C of G, a heterochromatic cycle of G is a cycle in which any pair of edges have distinct colors. Let d(c)(v), named the color degree of a vertex v, be defined as the maximum number of edges incident with v that have distinct colors. In this paper, some color degree conditions for the existence of heterochromatic cycles are obtained. (c) 2012 Elsevier Ltd. All rights reserved.
引用
收藏
页码：1958 / 1964
页数：7
相关论文
共 17 条
  • [1] Albert M., 1995, ELECTRON J COMB, V2
  • [2] Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints
    Alon, N
    Jiang, T
    Miller, Z
    Pritikin, D
    [J]. RANDOM STRUCTURES & ALGORITHMS, 2003, 23 (04) : 409 - 433
  • [3] Bondy J. A., 1976, Graduate Texts in Mathematics, V290
  • [4] Counting subgraphs - A new approach to the Caccetta-Haggkvist conjecture
    Bondy, JA
    [J]. DISCRETE MATHEMATICS, 1997, 165 : 71 - 80
  • [5] Broersma H, 2005, AUSTRALAS J COMB, V31, P299
  • [6] Caccetta L., 1978, Congress. Numer., P181
  • [7] Chen H, 2005, ELECTRON J COMB, V12
  • [8] Erdos P., 1983, Graphs and other combinatorial topics (Prague, 1982), V59, P54
  • [9] POLYCHROMATIC HAMILTON CYCLES
    FRIEZE, A
    REED, B
    [J]. DISCRETE MATHEMATICS, 1993, 118 (1-3) : 69 - 74
  • [10] PATH AND CYCLE SUB-RAMSEY NUMBERS AND AN EDGE-COLORING CONJECTURE
    HAHN, G
    THOMASSEN, C
    [J]. DISCRETE MATHEMATICS, 1986, 62 (01) : 29 - 33
12