Let G(C) be a graph of order n with an edge coloring C. A subgraph F of G(C) is rainbow if any pair of edges in F have distinct colors. This topic has been studied by various authors.
We have shown that if every vertex is adjacent to edges that are colored at least (n+1)/2 distinct colors, then there is a rainbow triangle. This bound is sharp. We also obtained sufficient condition for balanced bipartite graphs to have rainbow cycle of length 4. For this proposal of a PhD dissertation, we study sufficient conditions for edge colored graphs to have long rainbow cycles, and ones to have rainbow cycles of many different lengths.
Ref.
1. Hao Li and Guanghui Wang, Color degree and heterochromatic cycles in edge-colored graphs, European Journal of Combinatorics, Vol.33 issue 8 (Nov. (2012) 1958-1964.
2. H. Li, Rainbow C_3 and C_4 in edge-colored graphs, Discrete Math.
Online publication complete: 3-JAN-2013,
DOI information:10.1016/j.disc.2012.11.024
Context
Objectives
Work program
Extra information
Prerequisite
Détails
Expected funding
Institutional funding
Status of funding
Expected
Candidates
graph theory, combinatorics
Utilisateur
Hao.Li
Créé
Mardi 15 janvier 2013 17:39:36 CET
dernière modif.
Mardi 15 janvier 2013 17:39:36 CET
Fichiers joints
filename
créé
hits
filesize
Aucun fichier joint à cette fiche
Connexion
Ecole Doctorale Informatique Paris-Sud
Directrice
Nicole Bidoit Assistante
Stéphanie Druetta Conseiller aux thèses
Dominique Gouyou-Beauchamps
ED 427 - Université Paris-Sud
UFR Sciences Orsay
Bat 650 - aile nord - 417
Tel : 01 69 15 63 19
Fax : 01 69 15 63 87
courriel: ed-info à lri.fr