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 K 1 , 3 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, K 1 , 3 -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.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.