Premium
Domination in colored complete graphs
Author(s) -
Erdös P.,
Faudree R.,
Gyárfás A.,
Schelp R. H.
Publication year - 1989
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.3190130607
Subject(s) - combinatorics , mathematics , conjecture , colored , integer (computer science) , edge coloring , discrete mathematics , graph , computer science , graph power , line graph , materials science , composite material , programming language
We prove the following conjecture of Erdös and Hajnal: For any fixed positive integer t and for any 2‐coloring of the edges of k n , there exists X ⊂ v(K N ) such that |≦| and X monochromatically dominates all but at most n/2 t vertices of K n . In fact, X can be constructed by a fast greedy algorithm.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom