Rainbow path and color degree in edge colored graphs
type: Item
instance of: scholarly article
title: Rainbow path and color degree in edge colored graphs
zbMATH Open document ID: 1300.05094
published in: The Electronic Journal of Combinatorics
publication date: 2014-09-04T00:00:00Z
full work available at URL: https://arxiv.org/abs/1312.5067
full work available at URL: v21i1p46
review text: Summary: Let \(G\) be an edge colored graph. A rainbow path in \(G\) is a path in which all the edges are colored with distinct colors. Let \(d^c(v)\) be the color degree of a vertex \(v\) in \(G\), i.e. the number of distinct colors present on the edges incident on the vertex \(v\). Let \(t\) be the maximum length of a rainbow path in \(G\). \textit{H. Chen} and \textit{X. Li} [ibid. 12, No. 1, Research paper 33, 32 p. (2005; Zbl 1080.05047)] showed that if \(d^c \geq k \,\, (k\geq 8)\), for every vertex \(v\) of \(G\), then \(t \geq \left \lceil \frac{3 k}{5}\right \rceil + 1\). Unfortunately, the proof by Chen and Li is very long and comes to about 23 pages in the journal version. Chen and Li states in their paper that it was conjectured by Akira Saito, that \(t \geq \left \lceil \frac {2k} {3} \right \rceil\). They also state in their paper that they believe \(t \geq k - c\) for some constant \(c\). { }In this note, we give a short proof to show that \(t \geq \left \lceil \frac{3 k}{5}\right \rceil\), using an entirely different method. Our proof is only about 2 pages long. The draw-back is that our bound is less by 1, than the bound given by Chen and Li. We hope that the new approach adopted in this paper would eventually lead to the settlement of the conjectures by Saito and/or Chen and Li.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 6340144
zbMATH Keywords: edge colored graphs
zbMATH Keywords: rainbow path
zbMATH Keywords: color degree
MaRDI profile type: Publication
arXiv ID: 1312.5067
cites work: Q5294911
cites work: Long heterochromatic paths in edge-colored graphs
cites work: Rainbow and orthogonal paths in factorizations ofKn
cites work: Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
author: Anita Das
author: S. V. Subrahmanya
author: P. Suresh
description: scientific article; zbMATH DE number 6340144