Skip to main content

Publications supported by the ERC project CCOSA

All results supported by the ERC project CCOSA are freely available for download from the preprint server arXiv.

Authors and title arXiv Publication status
J. Balogh, P. Hu, B. Lidický, O. Pikhurko, B. Udvari, J. Volec: Minimum number of monotone subsequences of length 4 in permutations arXiv 1411.3024 Combinatorics, Probability and Computing 24 (2015), 658-679
J. Balogh, P. Hu, B. Lidický, F. Pfender, J. Volec, M. Young: Rainbow triangles in three-colored graphs arXiv 1408.5296 submitted
I. Bliznets, M. Cygan, P. Komosa, L. Mach: Kernelization lower bound for Permutation Pattern Matching arXiv 1406.1158 Information Processing Letters 115 (2015), 527-351
I. Bliznets, M. Cygan, P. Komosa, L. Mach, M. Pilipczuk: Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems arXiv 1508.05282 Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'16), pp. 1132-1151, ACM&SIAM, 2016
T. F. Bloom, A. Liebenau: Ramsey equivalence of Kn and Kn+Kn-1 arXiv 1508.03866 submitted
K. Choromanski, D. Falik, A. Liebenau, V. Patel, M. Pilipczuk: Excluding hooks and their complements arXiv 1508.00634 submitted
D. Christofides, K. Edwards, A. King: A note on hitting maximum and maximal cliques with a stable set arXiv 1109.3092 Journal of Graph Theory 73 (2013), 354-360
D. Christofides, D. Kráľ: First order convergence and roots arXiv 1403.3049 accepted to Combinatorics, Probability and Computing
D. Christofides, K. Markström: The thresholds for diameter 2 in random Cayley graphs arXiv 1108.3547 Random Structures and Algorithms 45 (2014), 218-235
M. Chudnovsky, Z. Dvořák, T. Klimošová, P. Seymour: Immersion in four-edge-connected graphs arXiv 1308.0827 Journal of Combinatorial Theory Ser. B 116 (2016), 208-218
J. W. Cooper, T. Kaiser, D. Kráľ, J. A. Noel: Weak regularity and finitely forcible graph limits arXiv 1507.00067 submitted
B. Csaba, D. Kühn, A. Lo, D. Osthus, A. Treglown: Proof of the 1-factorization and Hamilton decomposition conjectures   accepted to Memoirs of AMS
D. Kühn, A. Lo, D. Osthus, A. Treglown: Proof of the 1-factorization and Hamilton decomposition conjectures I: the two cliques case arXiv 1401.4159 merged to a single paper
B. Csaba, D. Kühn, A. Lo, D. Osthus, A. Treglown: Proof of the 1-factorization and Hamilton decomposition conjectures II: the bipartite case arXiv 1401.4164 merged to a single paper
B. Csaba, D. Kühn, A. Lo, D. Osthus, A. Treglown: Proof of the 1-factorization and Hamilton decomposition conjectures III: approximate decompositions arXiv 1401.4178 merged to a single paper
J. Cummings, D. Kráľ, F. Pfender, K. Sperfeld, A. Treglown, M. Young: Monochromatic triangles in three-coloured graphs arXiv 1206.1987 Journal of Combinatorial Theory Ser. B. 103 (2013), 489-503
F. Dross: Fractional triangle decompositions in graphs with large minimum degree arXiv 1503.08191 submitted
Z. Dvořák: A stronger structure theorem for excluded topological minors arXiv 1209.0129 submitted
Z. Dvořák: Constant-factor approximation of domination number in sparse graphs arXiv 1110.5190 European Journal of Combinatorics 34 (2013), 833-840
Z. Dvořák, K. Kawarabayashi: List-coloring embedded graphs arXiv 1210.7605 Proceedings of 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'13), pp. 1004-1012, ACM&SIAM, 2013
Z. Dvořák, T. Klimošová: Strong immersions and maximum degree arXiv 1304.0728 SIAM Journal on Discrete Mathematics 28 (2015), 177-187
Z. Dvořák, D. Kráľ, R. Thomas: Testing first-order properties for subclasses of sparse graphs arXiv 1109.5036 Journal of ACM 60 (2013), article no. 36
Z. Dvořák, V. Tůma: A dynamic data structure for counting subgraphs in sparse graphs arXiv 1209.0375 Lecture Notes in Computer Science vol. 8037, WADS'13, 2013, 304-315
L. Esperet, F. Kardoš, A. King, D. Kráľ, S. Norine: Exponentially many perfect matchings in cubic graphs arXiv 1012.2878 Advances in Mathematics 227 (2011), 1646-1664
J. Gajarský, P. Hliněný, T. Kaiser, D. Kráľ, M. Kupec, J. Obdržálek, S. Ordyniak, V. Tůma: First order limits of sparse graphs: Plane trees and path-width arXiv 1504.08122 submitted
R. Ganian, P. Hliněný, D. Kráľ, J. Obdržálek, J. Schwartz, J. Teska: FO model checking of interval graphs arXiv 1302.6043 Logical Methods in Computer Science 11 (2015), paper 4:11, 20pp
A. C. Giannopoulou, I. Salem, D. Zoros: Effective computation of immersion obstructions for unions of graph classes arXiv 1207.5636 Lecture Notes in Computer Science vol. 7357, SWAT'12, 2012, 165-176
R. Glebov, A. Grzesik, T. Klimošová, D. Kráľ: Finitely forcible graphons and permutons arXiv 1307.2444 Journal of Combinatorial Theory Series B 110 (2015), 112-135
R. Glebov, C. Hoppen, T. Klimošová, Y. Kohayakawa, D. Kráľ, H. Liu: Large permutations and parameter testing arXiv 1412.5622 submitted
R. Glebov, T. Klimošová, D. Kráľ: Infinite dimensional finitely forcible graphon arXiv 1404.2743 submitted
R. Glebov, D. Kráľ, J. Volec: A problem of Erdős and Sós on 3-graphs arXiv 1303.7372 accepted to Israel Journal of Mathematics
R. Glebov, D. Kráľ, J. Volec: Compactness and finite forcibility of graphons arXiv 1309.6695 submitted
H. Hatami, J. Hladký, D. Kráľ, S. Norine, A. Razborov: Non-three-colorable common graphs exist arXiv 1105.0307 Combinatorics, Probability and Computing 21 (2012), 734-742
H. Hatami, J. Hladký, D. Kráľ, S. Norine, A. Razborov: On the number of pentagons in triangle-free graphs arXiv 1102.1634 Journal of Combinatorial Theory Ser. A 120 (2013), 722-732
M. Hebdige, D. Kráľ: Third case of the Cyclic Coloring Conjecture arXiv 1501.06624 submitted
F. Kardoš, D. Kráľ, A. Liebenau, L. Mach: First order convergence of matroids arXiv 1501.06518 submitted
R. Kenyon, D. Kráľ, C. Radin, P. Winkler: A variational principle for permutations arXiv 1506.02340 submitted
T. Klimošová, D. Kráľ: Hereditary properties of permutations are strongly testable arXiv 1208.2624 Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'14), pp. 1164-1173, ACM&SIAM, 2014
D. Kráľ, C.-H. Liu, J.-S. Sereni, P. Whalen, Z. Yilma: A new bound for the 2/3 conjecture arXiv 1204.2519 Combinatorics, Probability and Computing 22 (2013), 384-393
D. Kráľ, L. Mach, J.-S. Sereni: A new lower bound based on Gromov's method of selecting heavily covered points arXiv 1108.0297 Discrete and Computational Geometry 48 (2012), 487-498
D. Kráľ, O. Pikhurko: Quasirandom permutations are characterized by 4-point densities arXiv 1205.3074 Geometric and Functional Analysis 23 (2013), 570-579
D. Kráľ, O. Serra, L. Vena: On the Removal Lemma for linear systems over Abelian groups arXiv 1106.4243 European Journal of Combinatorics 34 (2013), 248-259
L. M. Lovász: A short proof of the equivalence of left and right convergence for sparse graphs arXiv 1504.02892 European Journal of Combinatorics 53 (2016), 1-7
R. Lukoťka, J. Mazák, X. Zhu: Maximal 4-degenerated subgraph of a planar graph arXiv 1305.6195 submitted
L. Mach, T. Toufar: Amalgam width of matroids arXiv 1304.0299 Lecture Notes in Computer Science vol. 8246, IPEC'13, 2013, pp. 268-280
A. Treglown: On directed versions of the Hajnal-Szemerédi theorem arXiv 1406.3229 Combinatorics, Probability and Computing 24 (2015), 873-928
A. Treglown, Y. Zhao: Exact minimum degree thresholds for perfect matchings in uniform hypergraphs II arXiv 1210.7359 Journal of Combinatorial Theory Ser. A 120 (2013), 1463-1482

Funding info

ERC logo This project has received funding from the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no. 259385. FP7 logo