Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: clique minor

Sortuj według:

Ogranicz wyniki do:

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

Complete minors, independent sets, and chordal graphs

100%

Balogh J., Lenz J., Wu H.

Discussiones Mathematicae Graph Theory

2011

tom 31

nr 4

639-674

The Hadwiger number h(G) of a graph G is the maximum size of a complete minor of G. Hadwiger's Conjecture states that h(G) ≥ χ(G). Since χ(G) α(G) ≥ |V(G)|, Hadwiger's Conjecture implies that α(G) h(G) ≥ |V(G)|. We show that (2α(G) - ⌈log_{τ}(τα(G)/2)⌉) h(G) ≥ |V(G)| where τ ≍ 6.83. For graphs with α(G) ≥ 14, this improves on a recent result of Kawarabayashi and Song who showed (2α(G) - 2) h(G) ≥ |V(G) | when α(G) ≥ 3.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Balogh J.

1 Lenz J.

1 Wu H.

1 2011

Wyniki wyszukiwania

Complete minors, independent sets, and chordal graphs