FRACTIONALLY COLORING TOTAL GRAPHS

被引：14

作者：

KILAKOS, K

REED, B

机构：

[1] UNIV QUEBEC,DEPT MATH & INFORMAT,MONTREAL H3C 3P8,QUEBEC,CANADA

[2] CARNEGIE MELLON UNIV,DEPT MATH,PITTSBURGH,PA 15213

来源：

COMBINATORICA | 1993年 / 13卷 / 04期

关键词：

D O I：

10.1007/BF01303515

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Behzad and Vizing have conjectured that given any simPle graph of maximum degree DELTA, one can colour its edges and vertices with DELTA+2 colours so that no two adjacent vertices, or two incident edges, or an edge and either of its ends receive the same colour. We show that for any simple graph G, V(G) or E(G) can be fractionally coloured with DELTA+2 colours.

引用

页码：435 / 440

页数：6

共 7 条

[1] Behzad M., 1965, THESIS MICHIGAN STAT
[2] MAXIMUM MATCHING AND A POLYHEDRON WITH O'1-VERTICES
EDMONDS, J
[J]. JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL, 1965, B 69 (1-2): : 125 - +
[3] Fulkerson D. R., 1972, J COMBIN THEORY B, V12, P50
[4] AN UPPER BOUND FOR THE TOTAL CHROMATIC NUMBER
HIND, HR
[J]. GRAPHS AND COMBINATORICS, 1990, 6 (02) : 153 - 159
[5] FRACTIONAL TOTAL COLORING
RYAN, J
[J]. DISCRETE APPLIED MATHEMATICS, 1990, 27 (03) : 287 - 292
[6] TOTAL CHROMATIC NUMBER OF A GRAPH
VIJAYADITYA, N
[J]. JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 1971, 3 (APR): : 405 - +
[7] Vizing V.G., 1968, USPEKHIMAT NAUK, V23, P117

← 1 →