Inequalities for the Grundy chromatic number of graphs

被引：15

作者：

Zaker, Manouchehr ^{[1
]}

机构：

[1] Inst Adv Studies Basic Sci, Zanjan, Iran

来源：

DISCRETE APPLIED MATHEMATICS | 2007年 / 155卷 / 18期

关键词：

graph colorings; Grundy number; first-fit coloring;

D O I：

10.1016/j.dam.2007.07.002

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The Grundy (or First-Fit) chromatic number of a graph G is the maximum number of colors used by the First-Fit coloring of the graph G. In this paper we give upper bounds for the Grundy number of graphs in terms of vertex degrees, girth, clique partition number and for the line graphs. Next we show that if the Grundy number of a graph is large enough then the graph contains a subgraph of prescribed large girth and Grundy number. (c) 2007 Elsevier B.V. All rights reserved.

引用

页码：2567 / 2572

页数：6

共 11 条

[1] THE GREEDY ALGORITHM IS OPTIMAL FOR ONLINE EDGE COLORING [J].

BARNOY, A ;

MOTWANI, R ;

NAOR, J .

INFORMATION PROCESSING LETTERS, 1992, 44 (05) :251-253

[2]

Foreman K, 2005, PHYS THER SPORT, V6, P3, DOI 10.1016/j.ptsp.2004.09.003

[3] ONLINE AND 1ST FIT COLORINGS OF GRAPHS [J].

GYARFAS, A ;

LEHEL, J .

JOURNAL OF GRAPH THEORY, 1988, 12 (02) :217-227

[4]

Jensen T. R., 1995, Graph Coloring Problems

[5]

Kierstead H.A., 1988, SIAM J DISCRETE MATH, V1, P526

[6] ONLINE AND FIRST-FIT COLORING OF GRAPHS THAT DO NOT INDUCE P-5 [J].

KIERSTEAD, HA ;

PENRICE, SG ;

TROTTER, WT .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1995, 8 (04) :485-498

[7]

Kierstead HA, 1991, ONLINE ALGORITHMS P, P85

[8] Bounds for the b-chromatic number of some families of graphs [J].

Kouider, M ;

Zaker, M .

DISCRETE MATHEMATICS, 2006, 306 (07) :617-623

[9]

ZAKER M, 2006, DISCRETE MATH, V306, P3174

[10]

Zaker M, 2005, AUSTRALAS J COMB, V31, P325

← 1 2 →