Vertex-disjoint copies of K¯₄

Ken-ichi Kawarabayashi

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 2, page 249-262
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Ken-ichi Kawarabayashi. "Vertex-disjoint copies of K¯₄." Discussiones Mathematicae Graph Theory 24.2 (2004): 249-262. <http://eudml.org/doc/270476>.

@article{Ken2004,
abstract = { 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. },
author = {Ken-ichi Kawarabayashi},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {extremal graph theory; vertex disjoint copy; minimum degree},
language = {eng},
number = {2},
pages = {249-262},
title = {Vertex-disjoint copies of K¯₄},
url = {http://eudml.org/doc/270476},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Ken-ichi Kawarabayashi
TI - Vertex-disjoint copies of K¯₄
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 2
SP - 249
EP - 262
AB - 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.
LA - eng
KW - extremal graph theory; vertex disjoint copy; minimum degree
UR - http://eudml.org/doc/270476
ER -

References

top
  1. [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. Zbl0855.05085
  2. [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. Zbl0111.35901
  3. [3] Y. Egawa and K. Ota, Vertex-Disjoint in graphs, Discrete Math. 197/198 (1999), 225-246. Zbl0934.05077
  4. [4] Y. Egawa and K. Ota, Vertex-disjoint paths in graphs, Ars Combinatoria 61 (2001) 23-31. 
  5. [5] Y. Egawa and K. Ota, -factors in graphs, preprint. 
  6. [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. Zbl0217.02601
  7. [7] K. Kawarabayashi, K¯₄-factor in a graph, J. Graph Theory 39 (2002) 111-128, doi: 10.1002/jgt.10007. Zbl0992.05059
  8. [8] K. Kawarabayashi, F-factor and vertex disjoint F in a graph, Ars Combinatoria 62 (2002) 183-187. Zbl1073.05562
  9. [9] J. Komlós, Tiling Túran theorems, Combinatorica 20 (2000) 203-218. Zbl0949.05063

NotesEmbed ?

top

You must be logged in to post comments.