# Vertex-disjoint copies of K¯₄

Discussiones Mathematicae Graph Theory (2004)

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

## Access Full Article

top## Abstract

top## How to cite

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

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.