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 language | English |
---|---|
Pages (from-to) | 2001-2008 |
Journal | Graphs and combinatorics |
Volume | 32 |
Issue number | 5 |
DOIs | |
Publication status | Published - Sept 2016 |
Keywords
- Edge-colored graphs
- Color degree
- Rainbow triangles
- n/a OA procedure