Name
Abstract | ||
|---|---|---|
We investigate the following conjecture of Hehui Wu: for every tournament S, the class of S-free tournaments has bounded domination number. We show that the conjecture is false in general, but true when S is 2-colourable (that is, its vertex set can be partitioned into two transitive sets); the latter follows by a direct application of VC-dimension. Our goal is to go beyond this; we give a non-2-colourable tournament S that satisfies the conjecture. The key ingredient here (perhaps more interesting than the result itself) is that we overcome the unboundedness of the VC-dimension by showing that the set of shattered sets is sparse. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.jctb.2017.10.001 | Journal of Combinatorial Theory, Series B |
Keywords | DocType | Volume |
Tournament,Domination,VC-dimension | Journal | 130 |
ISSN | Citations | PageRank |
0095-8956 | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria Chudnovsky | 1 | 390 | 46.13 |
| ringi kim | 2 | 7 | 2.96 |
| Chun-hung Liu | 3 | 389 | 42.44 |
| Paul D. Seymour | 4 | 2786 | 314.49 |
| Stéphan Thomassé | 5 | 651 | 66.03 |