An Extension of the Hajnal-Szemeredi Theorem to Directed Graphs

被引：10

作者：

Czygrinow, Andrzej ^{[1
]}

DeBiasio, Louis ^{[2
]}

Kierstead, H. A. ^{[1
]}

Molla, Theodore ^{[3
]}

机构：

[1] Arizona State Univ, Sch Math & Stat Sci, Tempe, AZ 85287 USA

[2] Miami Univ, Oxford, OH 45056 USA

[3] Univ Illinois, Dept Math, Urbana, IL 61801 USA

来源：

COMBINATORICS PROBABILITY & COMPUTING | 2015年 / 24卷 / 05期

关键词：

CYCLES; PROOF;

D O I：

10.1017/S0963548314000716

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Hajnal and Szemeredi proved that every graph G with vertical bar G vertical bar = ks and delta(G) >= k(s - 1) contains k disjoint s-cliques; moreover this degree bound is optimal. We extend their theorem to directed graphs by showing that every directed graph (G) over right arrow with vertical bar(G) over right arrow vertical bar = ks and delta((G) over right arrow) >= 2k(s - 1) - 1 contains k disjoint transitive tournaments on s vertices, where delta((G) over right arrow) = min(nu is an element of V((G) over right arrow))d(-)(nu) + d(+)(nu). Our result implies the Hajnal-Szemeredi theorem, and its degree bound is optimal. We also make some conjectures regarding even more general results for multigraphs and partitioning into other tournaments. One of these conjectures is supported by an asymptotic result.

引用

页码：754 / 773

页数：20