Color Degree Sum Conditions for Rainbow Triangles in Edge-Colored Graphs

Ruonan Li, Bo Ning, Shenggui Zhang

    Research output: Contribution to journalArticleAcademicpeer-review

    4 Citations (Scopus)

    Abstract

    Let G be an edge-colored graph and v a vertex of G. The color degree of v is the number of colors appearing on the edges incident to v. A rainbow triangle in G is one in which all edges have distinct colors. In this paper, we first prove that an edge-colored graph on n vertices contains a rainbow triangle if the color degree sum of every two adjacent vertices is at least n+1n+1 . Afterwards, we characterize the edge-colored graphs on n vertices containing no rainbow triangles but satisfying that each pair of adjacent vertices has color degree sum at least n.
    Original languageEnglish
    Pages (from-to)2001-2008
    JournalGraphs and combinatorics
    Volume32
    Issue number5
    DOIs
    Publication statusPublished - Sep 2016

    Keywords

    • Edge-colored graphs
    • Color degree
    • Rainbow triangles

    Cite this