Rainbow path and color degree in edge colored graphs

MaRDI QIDQ405138zbMATH OpenFDO

Authors Anita Das, S. V. Subrahmanya, P. Suresh

Publication date 4 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.5067, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p46

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

rainbow pathcolor degreeedge colored graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Abstract: Let $G$ be an edge colored graph. A {it}{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$. Chen and Li showed that if $d^{c}geqk$, for every vertex $v$ of $G$, then $tgeqleftlceilfrac3k5ightceil+1$ (Long heterochromatic paths in edge-colored graphs, The Electronic Journal of Combinatorics 12 (2005), # R33, Pages:1-33.) Unfortunately, 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 $tgeleftlceilfrac2k3ightceil$. They also states in their paper that they believe $tgek-c$ for some constant $c$. In this note, we give a short proof to show that $tgeleftlceilfrac3k5ightceil$, 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.

Recommendations

• Color degree condition for long rainbow paths in edge-colored graphs
• The minimum color degree and a large rainbow cycle in an edge-colored graph.
• scientific article; zbMATH DE number 6303006
• Rainbow paths
• Rainbow triangles in edge-colored graphs

Cites work

• Long heterochromatic paths in edge-colored graphs
• Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
• On rainbow cycles in edge colored complete graphs
• Rainbow and orthogonal paths in factorizations of \(K_n\)

Cited in

(6)

• scientific article; zbMATH DE number 6303006 (Why is no real title available?)
• Rainbow degree-jump coloring of graphs
• Heterochromatic paths in edge colored graphs without small cycles and heterochromatic-triangle-free graphs
• Color degree condition for long rainbow paths in edge-colored graphs
• Long rainbow paths and rainbow cycles in edge colored graphs. A survey
• From colourful to rainbow paths in graphs: colouring the vertices

This page was built for publication: Rainbow path and color degree in edge colored graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405138)