Multiple vertex coverings by cliques

Wayne Goddard; Michael A. Henning

doi:10.1002/jgt.20047

Multiple vertex coverings by cliques

Wayne Goddard, Michael A. Henning

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

For positive integers m₁,..., m_k, let f(m ₁,..., 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 ith 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) = 2km- o(m). We also provide some exact values for f(m, n, 2).

Original language	English
Pages (from-to)	157-167
Number of pages	11
Journal	Journal of Graph Theory
Volume	48
Issue number	2
DOIs	https://doi.org/10.1002/jgt.20047
Publication status	Published - Feb 2005
Externally published	Yes

Keywords

Cliques
Covers
K-edge-coloring

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Geometry and Topology

Access to Document

10.1002/jgt.20047

Cite this

@article{4816eaed2b1240929ced1b7e598a068a,

title = "Multiple vertex coverings by cliques",

abstract = "For positive integers m1,..., mk, let f(m 1,..., mk 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 mi, all of whose edges have the ith 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) = 2km- o(m). We also provide some exact values for f(m, n, 2).",

keywords = "Cliques, Covers, K-edge-coloring",

author = "Wayne Goddard and Henning, {Michael A.}",

year = "2005",

month = feb,

doi = "10.1002/jgt.20047",

language = "English",

volume = "48",

pages = "157--167",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "2",

}

TY - JOUR

T1 - Multiple vertex coverings by cliques

AU - Goddard, Wayne

AU - Henning, Michael A.

PY - 2005/2

Y1 - 2005/2

N2 - For positive integers m1,..., mk, let f(m 1,..., mk 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 mi, all of whose edges have the ith 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) = 2km- o(m). We also provide some exact values for f(m, n, 2).

AB - For positive integers m1,..., mk, let f(m 1,..., mk 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 mi, all of whose edges have the ith 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) = 2km- o(m). We also provide some exact values for f(m, n, 2).

KW - Cliques

KW - Covers

KW - K-edge-coloring

UR - http://www.scopus.com/inward/record.url?scp=13444287807&partnerID=8YFLogxK

U2 - 10.1002/jgt.20047

DO - 10.1002/jgt.20047

M3 - Article

AN - SCOPUS:13444287807

SN - 0364-9024

VL - 48

SP - 157

EP - 167

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 2

ER -

Multiple vertex coverings by cliques

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this