Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: k-degenerate

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Structural results on maximal k-degenerate graphs

100%

Bickle A.

Discussiones Mathematicae Graph Theory

2012

tom 32

nr 4

659-676

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Bickle A.

1 2012

Wyniki wyszukiwania

Structural results on maximal k-degenerate graphs