Long heterochromatic paths in heterochromatic triangle free graphs

Simple item page
dc.creatorChen, He
dc.creatorLi, Xueliang
dc.date2008-04-29
dc.date.accessioned2026-07-07T09:35:48Z
dc.date.available2026-07-07T09:35:48Z
dc.descriptionIn this paper, graphs under consideration are always edge-colored. We consider long heterochromatic paths in heterochromatic triangle free graphs. Two kinds of such graphs are considered, one is complete graphs with Gallai colorings, i.e., heterochromatic triangle free complete graphs; the other is heterochromatic triangle free graphs with $k$-good colorings, i.e., minimum color degree at least $k$. For the heterochromatic triangle free graphs $K_n$, we obtain that for every vertex $v\in V(K_n)$, $K_n$ has a heterochromatic $v$-path of length at least $d^c(v)$; whereas for the heterochromatic triangle free graphs $G$ we show that if, for any vertex $v\in V(G)$, $d^c(v)\geq k\geq 6$, then $G$ a heterochromatic path of length at least $\frac{3k}{4}$.
dc.description12 pages
dc.identifierhttps://arxiv.org/abs/0804.4526
dc.identifierhttp://arxiv.org/abs/0804.4526
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/159953
dc.subjectCombinatorics
dc.subject05C38; 05C15
dc.titleLong heterochromatic paths in heterochromatic triangle free graphs
dc.typetext

Files

Collections

arXiv