PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2004 | 24 | 2 | 249-262
Tytuł artykułu

Vertex-disjoint copies of K¯₄

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Let G be a graph of order n. Let K¯ₗ be the graph obtained from Kₗ by removing one edge.
In this paper, we propose the following conjecture:
Let G be a graph of order n ≥ lk with δ(G) ≥ (n-k+1)(l-3)/(l-2)+k-1. Then G has k vertex-disjoint K¯ₗ.
This conjecture is motivated by Hajnal and Szemerédi's [6] famous theorem. In this paper, we verify this conjecture for l=4.
Wydawca
Rocznik
Tom
24
Numer
2
Strony
249-262
Opis fizyczny
Daty
wydano
2004
otrzymano
2002-08-31
poprawiono
2004-02-06
Twórcy
  • Department of Mathematics, Faculty of Science and Technology, Keio University, 3-14-1 Hiyoshi, Kohoku-ku, Yokohama 223-8522, Japan
Bibliografia
  • [1] N. Alon and R. Yuster, H-factor in dense graphs, J. Combin. Theory (B) 66 (1996) 269-282, doi: 10.1006/jctb.1996.0020.
  • [2] G.A. Dirac, On the maximal number of independent triangles in graphs, Abh. Math. Semin. Univ. Hamb. 26 (1963) 78-82, doi: 10.1007/BF02992869.
  • [3] Y. Egawa and K. Ota, Vertex-Disjoint $K_{1,3}$ in graphs, Discrete Math. 197/198 (1999), 225-246.
  • [4] Y. Egawa and K. Ota, Vertex-disjoint paths in graphs, Ars Combinatoria 61 (2001) 23-31.
  • [5] Y. Egawa and K. Ota, $K_{1,3}$-factors in graphs, preprint.
  • [6] A. Hajnal and E. Szemerédi, Proof of a conjecture of P. Erdős, Colloq. Math. Soc. János Bolyai 4 (1970) 601-623.
  • [7] K. Kawarabayashi, K¯₄-factor in a graph, J. Graph Theory 39 (2002) 111-128, doi: 10.1002/jgt.10007.
  • [8] K. Kawarabayashi, F-factor and vertex disjoint F in a graph, Ars Combinatoria 62 (2002) 183-187.
  • [9] J. Komlós, Tiling Túran theorems, Combinatorica 20 (2000) 203-218.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1229
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.