Rainbow path and color degree in edge colored graphs

Anita Das¹ ; S. V. Subrahmanya ; P. Suresh

¹Infosys Limited.

The electronic journal of combinatorics, Tome 21 (2014) no. 1

Résumé

Let $G$ be an edge colored graph. A rainbow pathin $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$. Chen and Li (2005) 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 \ge \left \lceil \frac {2k} {3} \right \rceil$. They also state in their paper that they believe $t \ge k - c$ for some constant $c$. In this note, we give a short proof to show that $t \ge \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.

Détail

DOI : 10.37236/3770

Classification : 05C15, 05C38
Mots-clés : edge colored graphs, rainbow path, color degree