Color neighborhood union conditions for long heterochromatic paths in edge-colored graphs (Q1010637)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Color neighborhood union conditions for long heterochromatic paths in edge-colored graphs
scientific article

    Statements

    Color neighborhood union conditions for long heterochromatic paths in edge-colored graphs (English)
    0 references
    0 references
    0 references
    7 April 2009
    0 references
    Summary: Let \(G\) be an edge-colored graph. A heterochromatic (rainbow, or multicolored) path of \(G\) is such a path in which no two edges have the same color. Let \(CN(v)\) denote the color neighborhood of a vertex \(v\) of \(G\). In a previous paper, we showed that if \(|CN(u)\cup CN(v)|\geq s\) (color neighborhood union condition) for every pair of vertices \(u\) and \(v\) of \(G\), then \(G\) has a heterochromatic path of length at least \(\lfloor{2s+4\over5}\rfloor\). In the present paper, we prove that \(G\) has a heterochromatic path of length at least \(\lceil{s+1\over2}\rceil\), and give examples to show that the lower bound is best possible in some sense.
    0 references
    edge coloring
    0 references
    heterochromatic path
    0 references
    color neighborhood
    0 references

    Identifiers