An upper bound for the chromatic number of line graphs

被引：14

作者：

King, A. D. ^{[1
]}

Reed, B. A. ^{[1
]}

Vetta, A. ^{[1
]}

机构：

[1] McGill Univ, Sch Comp Sci, Montreal, PQ H3A 2T5, Canada

来源：

EUROPEAN JOURNAL OF COMBINATORICS | 2007年 / 28卷 / 08期

关键词：

D O I：

10.1016/j.ejc.2007.04.014

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

It was conjectured by Reed [B. Reed, omega, alpha, and chi, Journal of Graph Theory 27 (1998) 177-212] that for any graph G, the graph's chromatic number chi(G) is bounded above by [Delta(G)+1+(omega)(G)/2], where Delta(G) and omega(G) are the rnaximum degree and clique number of G, respectively. In this paper we prove that this hound holds if G is the line graph of a multigraph. The proof yields a polynomial tirne algorithm that takes a line graph G and produces a colouring that achieves our bound. (C) 2007 Published by Elsevier Ltd.

引用

页码：2182 / 2187

页数：6

共 16 条

[1]

[Anonymous], 1964, DISKRET ANAL

[2] On colouring the nodes of a network [J].

Brooks, RL .

PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1941, 37 :194-197

[3] Improving a family of approximation algorithms to edge color multigraphs [J].

Caprara, A ;

Rizzi, R .

INFORMATION PROCESSING LETTERS, 1998, 68 (01) :11-15

[4] MAXIMUM MATCHING AND A POLYHEDRON WITH O'1-VERTICES [J].

EDMONDS, J .

JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL, 1965, B 69 (1-2) :125-+

[5]

Goldberg M.K., 1973, Diskretn. Anal., V23, P3

[6]

Hall P, 1935, J. Lond. Math. Soc., Vs1-10, P26, DOI DOI 10.1112/JLMS/S1-10.37.26

[7] THE NP-COMPLETENESS OF EDGE-COLORING [J].

HOLYER, I .

SIAM JOURNAL ON COMPUTING, 1981, 10 (04) :718-720

[8]

Kahn J, 2000, RANDOM STRUCT ALGOR, V17, P117, DOI 10.1002/1098-2418(200009)17:2<117::AID-RSA3>3.0.CO

[9]

2-9

[10] Asymptotics of the chromatic index for multigraphs [J].

Kahn, J .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1996, 68 (02) :233-254

← 1 2 →