Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

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

Gallai's innequality for critical graphs of reducible hereditary properties

100%

Mihók P., Skrekovski R.

Discussiones Mathematicae Graph Theory

2001

tom 21

nr 2

167-177

In this paper Gallai's inequality on the number of edges in critical graphs is generalized for reducible additive induced-hereditary properties of graphs in the following way. Let $𝓟₁,𝓟₂,...,𝓟ₖ$ (k ≥ 2) be additive induced-hereditary properties, $𝓡 = 𝓟₁ ∘ 𝓟₂ ∘ ... ∘𝓟ₖ$ and $δ = ∑_{i=1}^k δ(𝓟_i)$. Suppose that G is an 𝓡 -critical graph with n vertices and m edges. Then 2m ≥ δn + (δ-2)/(δ²+2δ-2)*n + (2δ)/(δ²+2δ-2) unless 𝓡 = 𝓞² or $G = K_{δ+1}$. The generalization of Gallai's inequality for 𝓟-choice critical graphs is also presented.

Hajós' theorem for list colorings of hypergraphs

81%

Benzaken C., Gravier S., Skrekovski R.

Discussiones Mathematicae Graph Theory

2003

tom 23

nr 2

207-213

A well-known theorem of Hajós claims that every graph with chromathic number greater than k can be constructed from disjoint copies of the complete graph $K_{k+1}$ by repeated application of three simple operations. This classical result has been extended in 1978 to colorings of hypergraphs by C. Benzaken and in 1996 to list-colorings of graphs by S. Gravier. In this note, we capture both variations to extend Hajós' theorem to list-colorings of hypergraphs.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Skrekovski R.

1 Benzaken C.

1 Gravier S.

1 Mihók P.

1 2003

1 2001

Wyniki wyszukiwania

Gallai's innequality for critical graphs of reducible hereditary properties

Hajós' theorem for list colorings of hypergraphs