Geodesic
Structural results on maximal k-degenerate graphs
Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 4, pp. 659-676

Voir la notice de l'article provenant de la source Library of Science

A graph is k-degenerate if its vertices can be successively deleted so that when deleted, each has degree at most k. These graphs were introduced by Lick and White in 1970 and have been studied in several subsequent papers. We present sharp bounds on the diameter of maximal k-degenerate graphs and characterize the extremal graphs for the upper bound. We present a simple characterization of the degree sequences of these graphs and consider related results. Considering edge coloring, we conjecture that a maximal k-degenerate graph is class two if and only if it is overfull, and prove this in some special cases. We present some results on decompositions and arboricity of maximal k-degenerate graphs and provide two characterizations of the subclass of k-trees as maximal k-degenerate graphs. Finally, we define and prove a formula for the Ramsey core numbers.
Keywords: k-degenerate, k-core, k-tree, degree sequence, Ramsey number 
@article{DMGT_2012_32_4_a4,
     author = {Bickle, Allan},
     title = {Structural results on maximal k-degenerate graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {659--676},
     publisher = {mathdoc},
     volume = {32},
     number = {4},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a4/}
}
TY  - JOUR
AU  - Bickle, Allan
TI  - Structural results on maximal k-degenerate graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2012
SP  - 659
EP  - 676
VL  - 32
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a4/
LA  - en
ID  - DMGT_2012_32_4_a4
ER  - 
%0 Journal Article
%A Bickle, Allan
%T Structural results on maximal k-degenerate graphs
%J Discussiones Mathematicae. Graph Theory
%D 2012
%P 659-676
%V 32
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a4/
%G en
%F DMGT_2012_32_4_a4
Bickle, Allan. Structural results on maximal k-degenerate graphs. Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 4, pp. 659-676. http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a4/