Premium
Highly connected monochromatic subgraphs of multicolored graphs
Author(s) -
Liu Henry,
Morris Robert,
Prince Noah
Publication year - 2009
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.20365
Subject(s) - combinatorics , mathematics , monochromatic color , graph , prime (order theory) , discrete mathematics , physics , optics
We consider the following question of Bollobás: given an r ‐coloring of E ( K n ), how large a k ‐connected subgraph can we find using at most s colors? We provide a partial solution to this problem when s =1 (and n is not too small), showing that when r =2 the answer is n −2 k +2, when r =3 the answer is ⌊( n − k )/2⌋+1 or ⌈( n − k )/2⌉+1, and when r −1 is a prime power then the answer lies between n /( r −1)−11( k 2 − k ) r and ( n − k +1)/( r −1)+ r . The case s ≥2 is considered in a subsequent paper (Liu et al.[6]), where we also discuss some of the more glaring open problems relating to this question. © 2009 Wiley Periodicals, Inc. J. Graph Theory 61: 22‐44, 2009