Premium
Complete graphs with no rainbow tree
Author(s) -
SchlagePuchta JanChristoph,
Wagner Peter
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22479
Subject(s) - rainbow , combinatorics , mathematics , pairwise comparison , embedding , graph , discrete mathematics , 1 planar graph , chordal graph , computer science , artificial intelligence , statistics , physics , quantum mechanics
We study colorings of the edges of the complete graph K n . For some graph H , we say that a coloring contains a rainbow H , if there is an embedding of H into K n , such that all edges of the embedded copy have pairwise distinct colors. The main emphasis of this paper is a classification of those forbidden rainbow graphs that force a low number of vertices of a high color degree, along with some specifications and more general information in certain cases. Those graphs turn out to be of two special types of trees of small diameter.