On a graph colouring problem

被引：8

作者：

Cochand, M ^{[1
]}

Karolyi, G ^{[1
]}

机构：

[1] ETH Zentrum, Dept Math, Inst Operat Res, CH-8092 Zurich, Switzerland

来源：

DISCRETE MATHEMATICS | 1999年 / 194卷 / 1-3期

关键词：

D O I：

10.1016/S0012-365X(98)00060-0

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A graph G = (V, E) is said to be k-emulsive if it admits an edge-colouring psi:E --> [k] = {1,2,...,k} such that, for any vertex-colouring phi : V --> [k] there exists an edge e = {x, y} such that phi(x)= phi(y)= psi(e). We show, by construction, that the complete graph on (1 + o(1))k(2) vertices is k-emulsive. This settles a question raised by Cochand and Duchet. (C) 1999 Published by Elsevier Science B.V. All rights reserved.

引用

页码：249 / 252

页数：4

共 7 条

[1]

ALON N, 1992, PROBABILISTIC METHOD

[2]

[Anonymous], C MATH SOC J BOLYAI

[3] The difference between consecutive primes [J].

Baker, RC ;

Harman, G .

PROCEEDINGS OF THE LONDON MATHEMATICAL SOCIETY, 1996, 72 :261-280

[4] RAMSEY PROPERTIES OF ORIENTATIONS OF GRAPHS [J].

BRIGHTWELL, GR ;

KOHAYAKAWA, Y .

RANDOM STRUCTURES & ALGORITHMS, 1993, 4 (04) :413-428

[5]

Cochand M., 1989, IRREGULARITIES PARTI, V8, P39, DOI [10.1007/978-3-642-61324-1_3, DOI 10.1007/978-3-642-61324-13]

[6]

RODL V, 1976, GRAPHS HYPERGRAPHS B, P211

[7]

Rodl V., 1989, SIAM Journal of Discrete Mathematics, V2, P402

← 1 →