Premium
Multiple vertex coverings by cliques
Author(s) -
Goddard Wayne,
Henning Michael A.
Publication year - 2005
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.20047
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , cardinality (data modeling) , discrete mathematics , computer science , data mining
For positive integers m 1 ,…, m k , let f ( m 1 ,…, m k ) be the minimum order of a graph whose edges can be colored with k colors such that every vertex is in a clique of cardinality m i , all of whose edges have the i th color for all i = 1,2,…, k . The value for k = 2 was determined by Entringer et al. ( J Graph Theory 24 (1997), 21–23). We show that if k is fixed then f ( m ,…, m ) = 2 km – o ( m ). We also provide some exact values for f ( m , n , 2). © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 157–167, 2005