Discussiones Mathematicae Graph Theory 32(4) (2012)
659-676

doi: 10.7151/dmgt.1637

Allan Bickle
Department of Mathematics |

**Keywords:** *k*-degenerate, *k*-core, *k*-tree, degree sequence, Ramsey number

**2010 Mathematics Subject Classification:** 05C75.

[1] | A. Bickle, The k-Cores of a graph. Ph.D. Dissertation, Western Michigan University, 2010. |

[2] | M. Borowiecki, J. Ivančo, P. Mihók and G. Semanišin, Sequences realizable by maximal k-degenerate graphs, J. Graph Theory 19 (1995) 117--124, doi: 10.1002/jgt.3190190112. |

[3] | G. Chartrand and L. Lesniak, Graphs and Digraphs, (4th ed.) (CRC Press, 2005). |

[4] | B. Chen, M. Matsumoto, J. Wang, Z. Zhang and J. Zhang, A short proof of Nash-Williams' Theorem for the arboricity of a graph, Graphs Combin. 10 (1994) 27--28, doi: 10.1007/BF01202467. |

[5] | A.G. Chetwynd and A.J.W. Hilton, Star multigraphs with , Math. Proc. Cambridge Math. Soc. 3 vertices of maximum degree 100 (1986) 303--317, doi: 10.1017/S030500410006610X . |

[6] | G.A. Dirac , Homomorphism theorems for graphs, Math. Ann. 153 (1964) 69--80, doi: 10.1007/BF01361708. |

[7] | Z. Filáková, P. Mihók and G. Semanišin, A note on maximal k-degenerate graphs, Math. Slovaca 47 (1997) 489--498. |

[8] | Z. Goufei, A note on graphs of class , Discrete Math. 1 263 (2003) 339--345, doi: 10.1016/S0012-365X(02)00793-8 . |

[9] | S. Hakimi, J. Mitchem and E. Schmeichel, Short proofs of theorems of Nash-Williams and Tutte, Ars Combin. 50 (1998) 257--266. |

[10] | R. Klein and J. Schonheim, Decomposition of , Combinatorics and Graph Theory Hefei 6-27, World Scientific. Singapore (New Jersey, London, Hong Kong, April 1992) 141--155.K into degenerate graphs_{n} |

[11] | D.R. Lick and A.T. White, k-degenerate graphs, Canad. J. Math. 22 (1970) 1082--1096, doi: 10.4153/CJM-1970-125-1 . |

[12] | W. Mader , , Combinatorica 3n-5 edges do force a subdivision of K_{5} 18 (1998) 569--595, doi: 10.1007/s004930050041. |

[13] | J. Mitchem, Maximal k-degenerate graphs, Util. Math. 11 (1977) 101--106. |

[14] | C.St.J.A. Nash-Williams, Decomposition of finite graphs into forests, J. London Math. Soc. 39 (1964) 12, doi: 10.1112/jlms/s1-39.1.12 . |

[15] | H.P. Patil , A note on the edge-arboricity of maximal k-degenerate graphs, Bull. Malays. Math Sci. Soc.(2) 7 (1984) 57--59. |

[16] | S.B. Seidman, Network structure and minimum degree, Social Networks 5 (1983) 269--287, doi: 10.1016/0378-8733(83)90028-X. |

[17] | J.M.S. Simões-Pereira , A survey of k-degenerate graphs, Graph Theory Newsletter 5 (1976) 1--7. |

[18] | West D., Introduction to Graph Theory, (2nd ed.) (Prentice Hall, 2001). |

Received 9 June 2011

Revised 13 December 2011

Accepted 13 December 2011