Orderings on graphs and game coloring number

被引:65
作者
Kierstead, HA [1 ]
Yang, DQ [1 ]
机构
[1] Arizona State Univ, Dept Math & Stat, Tempe, AZ 85287 USA
来源
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS | 2003年 / 20卷 / 03期
关键词
k-coloring number; k-game coloring number; planar graphs;
D O I
10.1023/B:ORDE.0000026489.93166.cb
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Many graph theoretic algorithms rely on an initial ordering of the vertices of the graph which has some special properties. We discuss new ways to measure the quality of such orders, give methods for constructing high quality orders, and provide applications for these orders. While our main motivation is the study of game chromatic number, there have been other applications of these ideas and we expect there will be more.
引用
收藏
页码:255 / 264
页数:10
相关论文
共 14 条
[1]  
[Anonymous], 1993, SURVEYS COMBINATORIC
[2]  
[Anonymous], ELECT J COMBIN
[3]  
BOLLOBAS B, 1994, UNPUB PROOF CONJECTU
[4]   GRAPHS WITH LINEARLY BOUNDED RAMSEY NUMBERS [J].
CHEN, GT ;
SCHELP, RH .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1993, 57 (01) :138-149
[5]   A bound for the game chromatic number of graphs [J].
Dinski, T ;
Zhu, XD .
DISCRETE MATHEMATICS, 1999, 196 (1-3) :109-115
[6]  
FAIGLE U, 1993, ARS COMBINATORIA, V35, P143
[7]   Marking games and the oriented game chromatic number of partial k-trees [J].
Kierstead, HA ;
Tuza, Z .
GRAPHS AND COMBINATORICS, 2003, 19 (01) :121-129
[8]   A simple competitive graph coloring algorithm [J].
Kierstead, HA .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2000, 78 (01) :57-68
[9]   PLANAR GRAPH-COLORING WITH AN UNCOOPERATIVE PARTNER [J].
KIERSTEAD, HA ;
TROTTER, WT .
JOURNAL OF GRAPH THEORY, 1994, 18 (06) :569-584
[10]  
KIERSTEAD HA, 2002, UNPUB ACYCLIC COLORI