Orderings on graphs and game coloring number
作者： H. A. Kierstead , Daqing Yang
DOI: 10.1023/B:ORDE.0000026489.93166.CB
关键词: List coloring 、 Greedy coloring 、 Edge coloring 、 Fractional coloring 、 Graph coloring 、 Graph power 、 Graph homomorphism 、 Discrete mathematics 、 Comparability graph 、 Mathematics
摘要: Many graph theoretic algorithms rely on an initial ordering of the vertices which has some special properties. We discuss new ways to measure quality such orders, give methods for constructing high and provide applications these orders. While our main motivation is study game chromatic number, there have been other ideas we expect will be more.
springer.com
elsevier.com
sci-hub.se 参考文章(11)
Charles Dunn, H.A. Kierstead, A simple competitive graph coloring algorithm III Journal of Combinatorial Theory, Series B. ,vol. 78, pp. 137- 150 ,(2004) , 10.1016/J.JCTB.2004.03.010
B. Bollobás, A. Thomason, Proof of a conjecture of Mader, Erdös and Hajnal on topological complete subgraphs The Journal of Combinatorics. ,vol. 19, pp. 883- 887 ,(1998) , 10.1006/EUJC.1997.0188
H. A. Kierstead, W. T. Trotter, Planar graph coloring with an uncooperative partner Journal of Graph Theory. ,vol. 18, pp. 569- 584 ,(1994) , 10.1002/JGT.3190180605
János Komlós, Endre Szemerédi, Topological Cliques in Graphs Combinatorics, Probability & Computing. ,vol. 5, pp. 79- 90 ,(1994) , 10.1017/S096354830000184X
Noga Alon, Restricted colorings of graphs Surveys in combinatorics, 1993. pp. 1- 33 ,(1993) , 10.1017/CBO9780511662089.002
Walter Kern, H. Kierstead, W.T. Trotter, U. Faigle, On the game chromatic number of some classes of graphs Ars Combinatoria. ,vol. 35, pp. 143- 150 ,(1993)
G.T. Chen, R.H. Schelp, Graphs with linearly bounded Ramsey numbers Journal of Combinatorial Theory, Series B. ,vol. 57, pp. 138- 149 ,(1993) , 10.1006/JCTB.1993.1012
Xuding Zhu, The Game Coloring Number of Planar Graphs Journal of Combinatorial Theory, Series B. ,vol. 75, pp. 245- 258 ,(1999) , 10.1006/JCTB.1998.1878
Zs. Tuza, H.A. Kierstead, Marking games and the oriented game chromatic number of partial k-trees Graphs and Combinatorics. ,vol. 19, pp. 121- 129 ,(2003) , 10.1007/S00373-002-0489-5
Xuding Zhu, The game coloring number of pseudo partial k -trees Discrete Mathematics. ,vol. 215, pp. 245- 262 ,(2000) , 10.1016/S0012-365X(99)00237-X