Gallai colorings of non-complete graphs |
| |
Authors: | Andrá s Gyá rfá s |
| |
Affiliation: | a Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, P.O. Box 63, Budapest, H-1518, Hungary b Computer Science Department, Worcester Polytechnic Institute, Worcester, MA, 01609, USA |
| |
Abstract: | Gallai-colorings of complete graphs-edge colorings such that no triangle is colored with three distinct colors-occur in various contexts such as the theory of partially ordered sets (in Gallai’s original paper), information theory and the theory of perfect graphs. We extend here Gallai-colorings to non-complete graphs and study the analogue of a basic result-any Gallai-colored complete graph has a monochromatic spanning tree-in this more general setting. We show that edge colorings of a graph H without multicolored triangles contain monochromatic connected subgraphs with at least (α(H)2+α(H)−1)−1|V(H)| vertices, where α(H) is the independence number of H. In general, we show that if the edges of an r-uniform hypergraph H are colored so that there is no multicolored copy of a fixed F then there is a monochromatic connected subhypergraph H1⊆H such that |V(H1)|≥c|V(H)| where c depends only on F, r, and α(H). |
| |
Keywords: | Gallai colorings Monochromatic connected components |
本文献已被 ScienceDirect 等数据库收录! |
|