EuroComb'11
Budapest, August 29-September 2, 2011
Rényi Institute

List of accepted talks

  • Andrew Treglown, Daniela Kühn and Deryk Osthus: Matchings in 3-uniform hypergraphs of large minimum vertex degree
  • Gadi Aleksandrowicz and Gill Barequet: The Growth Rate of High-Dimensional Tree Polycubes
  • Harout Aydinian and Péter L. Erdős: On two-part Sperner systems for regular posets
  • Ingo Schiermeyer, Maria Koch and Stephan Matos Camacho: Algorithmic approaches for the minimum rainbow subgraph problem
  • Matthew J. Samuel: Abstract root systems and intervals in weak Bruhat order
  • Younjin Kim and Zoltán Füredi: Minimum Ck-saturated graphs
  • Radoslav Fulek and Andrew Suk: On disjoint crossing families in geometric graphs
  • Delia Garijo, Andrew Goodall and Jaroslav Nešetřil: Contractors for flows
  • Ameera Chowdhury: On a Conjecture of Frankl and Füredi
  • Torsten Mütze and Reto Spöhel: On the path-avoidance vertex-coloring game
  • Graham Brightwell, Gérard Cohen, Emanuela Fachini, Marianne Fairthorne, János Körner, Gábor Simonyi and Ágnes Tóth: Permutation Capacities and Oriented Infinite Paths
  • Kazuyuki Amano: On Extremal k-CNF Formulas
  • János Barát, Zoltán Füredi, Ida Kantor, Younjin Kim and Balázs Patkós: Large Bd-free and union-free subfamilies
  • Dieter Rautenbach and Jayme Szwarcfiter: Unit Interval Graphs - A Story with Open Ends
  • Sang-il Oum: Rank-width and Well-quasi-ordering of Skew-Symmetric or Symmetric Matrices
  • Giuseppe O. Longo and Andrea Sgarro: Unruly codes with unruly distances raise (combinatorial) problems
  • János Körner, Silvia Messuti and Gábor Simonyi: Families of Very Different Paths
  • Vadim Levit and Eugen Mandrescu: A Characterization of König-Egerváry Graphs Using a Common Property of All Maximum Matchings
  • Nikolaos Fountoulakis, Ross J. Kang and Colin McDiarmid: Largest sparse subgraphs of random graphs
  • Tomás Feder, Pavol Hell and Shekoofeh Nekooei Rizi: Partitioning Chordal Graphs
  • Anna de Mier, Andrew Goodall, Steven Noble and Marc Noy: The Tutte polynomial characterizes simple outerplanar graphs
  • Ilia Averbouch, Tomer Kotek, Johann A. Makowsky and Elena V. Ravve: The Universal Edge Elimination Polynomial and the Dichromatic Polynomial
  • Rommel Barbosa, Erika Coelho, Mitre Dourado, Dieter Rautenbach and Jayme Szwarcfiter: On the Carathéodory Number for the Convexity of Paths of Order Three
  • Gyula Y. Katona and Nándor Sieben: Bounds on the Rubbling and Optimal Rubbling Numbers of Graphs
  • Hervé Hocquard and Mickaël Montassier: Adjacent vertex-distinguishing edge coloring of graphs with maximum degree at least five
  • Deryk Osthus, Daniela Kühn and Richard Mycroft: A proof of Sumner's universal tournament conjecture for large tournaments
  • Michael Drmota and Marc Noy: Universal exponents and tail estimates in the enumeration of planar maps
  • Mirka Miller, Oudone Phanalasy and Joe Ryan: All graphs have total antimagic labelings
  • Shinya Fujita, Henry Liu and Colton Magnant: Rainbow k-connection in Dense Graphs
  • Anastasia Rozovskaya and Dmitry Shabanov: On colorings of non-uniform hypergraphs without short cycles
  • Tobias Christ, Dömötör Pálvölgyi and Miloš Stojaković: Digitalizing line segments
  • Vadim Levit and David Tankus: Lower Bounds on the Odds Against Tree Spectral Sets
  • Shinya Fujita and Ken-Ichi Kawarabayashi: High connectivity keeping connected subgraph
  • David Pritchard and Filip Morić: Counting large distances in convex polygons: A computational approach
  • Vladimir Blinovsky: Complete Intersection Theorem for Permutations
  • Károly Bezdek: Contact numbers for congruent sphere packings
  • Archontia Giannopoulou and Dimitrios Thilikos: A min-max theorem for LIFO-search
  • Hervé Hocquard, Pascal Ochem and Petru Valicov: Bounds and complexity results for strong edge colouring of subcubic graphs
  • Agnieszka Polak and Daniel Simson: Symbolic and numerical computation in determining P-critical unit forms and Tits P-critical posets
  • Pavle Blagojević, Boris Bukh and Roman Karasev: Turán numbers for Ks,t-free graphs: topological obstructions and algebraic constructions
  • Antoni Lozano: Symmetry Breaking in Tournaments
  • Vasco Mano, Enide Martins and Luís Vieira: Feasibility Conditions on the Parameters of a Strongly Regular Graph
  • Asaf Ferber, Dan Hefetz and Michael Krivelevich: Fast embedding of spanning trees in biased Maker-Breaker games
  • Kolja Knauer, Juan José Montellano-Ballesteros and Ricardo Strausz: A graph-theoretical axiomatization of oriented matroids
  • Noah Streib and William Trotter: Dimension and Height for Posets with Planar Cover Graphs
  • Luca Gugelmann and Reto Spöhel: On Balanced Coloring Games in Random Graphs
  • Athanassios Koutsonas, Koichi Yamazaki and Dimitrios Thilikos: Outerplanar Obstructions for Matroid Pathwidth
  • Guillem Perarnau and Oriol Serra: Rainbow Matchings: existence and counting
  • Ángeles Carmona, Enrique Bendito, Andrés M. Encinas and Margarida Mitjana: On the Moore-Penrose inverse of distance-regular graphs
  • Maria Bras-Amorós: Ordinarization of Numerical Semigroups
  • Marianna Bolla: Spectra and structure of weighted graphs
  • Raquel Águeda, Valentin Borozan, Marina Groshaus, Gervais Mendy, Yannis Manoussakis and Leandro Montero: Proper Hamiltonian Paths in Edge-Colored Multigraphs
  • Florent Foucaud, Sylvain Gravier, Reza Naserasr, Aline Parreau and Petru Valicov: Edge identifying codes
  • Atsuhiro Nakamoto and Ryuichi Mori: Linear number of diagonal flips in triangulations on surfaces
  • Vladimir Shlyk: Vertex Structure of Master Corner Polyhedra
  • Richard Anstee, Miguel Raggi and Attila Sali: Forbidden Configurations: Boundary Cases
  • Konstantinos Panagiotou, Reto Spöhel, Angelika Steger and Henning Thomas: Explosive Percolation in Erdős-Rényi-Like Random Graph Processes
  • Peter Allen, Julia Böttcher, Jan Hladký and Diana Piguet: A density Corrádi-Hajnal theorem
  • Tobias Christ, Andrea Francke, Heidi Gebauer, Jiří Matoušek and Takeaki Uno: A Doubly Exponentially Crumbled Cake
  • Pablo Soberón and Ricardo Strausz: On Tverberg's Theorem
  • Csilla Bujtás and Zsolt Tuza: Combinatorial batch codes: Extremal problems under Hall-type conditions
  • Alexey Pokrovskiy: Partitioning 3-coloured complete graphs into three monochromatic paths
  • L. Sunil Chandran, Anita Das, Deepak Rajendraprasad and Nithin M. Varma: Rainbow Connection Number and Connected Dominating Sets
  • Zoltán Füredi: Linear paths and trees in uniform hypergraphs
  • Tomoki Namamigawa and Norihide Tokushige: Counting lattice paths via a cycle lemma
  • Gary MacGillivray, André Raspaud and Jacobus Swarts: Obstructions to Locally Injective Oriented Colourings
  • Arash Asadi and Spencer Backman: Chip-Firing and Riemann-Roch Theory for Directed Graphs
  • Clément Charpentier, Mickaël Montassier and André Raspaud: Minmax degree of planar graphs
  • Nestor Nestoridis and Dimitrios Thilikos: Square Roots of Minor Closed Graph Classes
  • Benjamin Doerr, Mahmoud Fouz and Tobias Friedrich: Social Networks Spread Rumors in Sublogarithmic Time
  • Benjamin Doerr and Mahmoud Fouz: Asymptotically Optimal Randomized Rumor Spreading
  • Sagnik Sen: 2-dipath and oriented L(2,1)-labelings of some families of oriented planar graphs
  • Roman Čada, Shuya Chiba and Kiyoshi Yoshimoto: 2-factors in claw-free graphs
  • Cristina Araúz, Ángeles Carmona, Andrés M. Encinas and Enrique Bendito: The Kirchhoff Index of Cluster Networks
  • Edward Kim: Polyhedral graph abstractions and an approach to the Linear Hirsch Conjecture
  • Arnaud Pêcher and Annegret Wagler: Computing the clique number of a-perfect graphs in polynomial time
  • Marc Cámara, Cristina Dalfó, Josep Fàbrega, Miquel Ángel Fiol and Ernest Garriga: Edge-distance-regular graphs
  • Petr Golovach, Marcin Kamiński, Daniël Paulusma and Dimitrios Thilikos: Lift contractions
  • Carlos Hoppen, Yoshiharu Kohayakawa and Hanno Lefmann: Edge colorings of graphs avoiding some fixed monochromatic subgraph with linear Turán number
  • Kim Marshall, Mirka Miller and Joe Ryan: Extremal Graphs without Cycles of Length 8 or Less
  • Naoki Matsumoto and Atsuhiro Nakamoto: Transformations in hexangulations on the sphere
  • Subramanya Bharadwaj, Sathish Govindarajan and Karmveer Sharma: On the Erdős-Szekeres n-interior point problem
  • Peter Borg: The maximum sum and product of sizes of cross-intersecting families
  • Marcin Gąsiorek and Daniel Simson: Programming in PYTHON and an algorithmic description of positive wandering on one-peak posets
  • Balázs Keszegh and Dömötör Pálvölgyi: Octants are Cover Decomposable
  • Hidehiro Shinohara and Tadashi Sakuma: On circular thin Lehman matrices
  • Demetres Christofides, Jan Hladký and András Máthé: A proof of the dense version of Lovász conjecture
  • Julia Böttcher, Anusch Taraz and Andreas Würfl: Induced C5-free graphs of fixed density: counting and homogeneous sets
  • Marie Albenque, Éric Fusy and Dominique Poulalhon: On symmetric quadrangulations
  • Kunal Dutta and C. R. Subramanian: On induced acyclic subgraphs in sparse random digraphs
  • Arash Asadi, Luke Postle and Robin Thomas: Minor-Minimal Non-Projective Planar Graphs with an Internal 3-Separation
  • Julio Araujo, Victor Campos, Frédéric Giroire, Leonardo Sampaio and Ronan Soares: On the hull number of some graph classes
  • Jamie Smith: On the Limitations of Graph Invariants Inspired by Quantum Walks
  • Luca Gugelmann, Yury Person, Angelika Steger and Henning Thomas: A Randomized Version of Ramsey's Theorem
  • Marthe Bonamy, Benjamin Lévêque and Alexandre Pinlou: 2-distance coloring of sparse graphs
  • Susanna F. de Rezende, Cristina G. Fernandes, Daniel M. Martin and Yoshiko Wakabayashi: Intersection of Longest Paths in a Graph
  • Hiệp Hàn, Yury Person and Mathias Schacht: Note on forcing pairs
  • Viola Mészáros: An upper bound on the size of separated matchings
  • Edita Máčajová and Martin Škoviera: Determining the flow numbers of signed eulerian graphs
  • Antônio Bastos, Carlos Hoppen, Yoshiharu Kohayakawa and Rudini Sampaio: Every hereditary permutation property is testable
  • Richard Wilson and Tony Wong: Diagonal forms for incidence matrices and zero-sum Ramsey theory
  • Zoltán Füredi, Ida Kantor, Angelo Monti and Blerina Sinaimeri: Reverse-free codes and permutations
  • Michal Kotrbčík: Maximum genus of regular graphs
  • Ken-Ichi Kawarabayashi and Kenta Ozeki: Hamilton cycles in 4-connected triangulations of the torus
  • Peter Whalen: Three coloring planar graphs without cycles of length from 4 to 6 or seven cycles with close triangles
  • Edita Máčajová and Edita Rollová: On the flow numbers of signed complete and complete bipartite graphs
  • Filippo Disanto, Enrica Duchi, Simone Rinaldi and Gilles Schaeffer: Permutations with few internal points
  • Oriol Serra and Lluís Vena: On the number of monochromatic solutions of integer linear systems on Abelian groups
  • Petr Gregor, Riste Škrekovski and Vida Vukašinović: On the queue-number of the hypercube
  • Lali Barrière, Clemens Huemer, Dieter Mitsche and David Orden: On the Fiedler value of large planar graphs
  • Jiří Fink and Petr Gregor: Linear extension diameter of subposets of Boolean lattice induced by two levels
  • Uwe Leck and Ian Roberts: Minimizing the weight of the union-closure of uniform families of sets
  • Jesús Leaños, Oswin Aichholzer, Bernardo Ábrego, Silvia Fernández-Merchant and Gelasio Salazar: There is a unique crossing-minimal rectilinear drawing of K18
  • Bojan Mohar and Tamon Stephen: Expected Crossing Numbers
  • Márcia R. Cerioli, Hugo Nobrega and Petrucio Viana: On characterizations by nice forbidding sets
  • Colin McDiarmid and Tobias Müller: Counting disk graphs
  • Cédric Bentz, Marie-Christine Costa, Dominique de Werra, Christophe Picouleau and Bernard Ries: Minimum d-Transversals of Maximum-Weight Stable Sets in Trees
  • Robin Christian, Bruce Richter and Gelasio Salazar: Asymptotically settling Zarankiewicz's Conjecture in finite time, for each m
  • David Hartman and Dragan Mašulović: Towards finite homomorphism-homogeneous relational structures
  • Bartłomiej Bosek, Tomasz Krawczyk and Grzegorz Matecki: Forbidden structures for efficient First-Fit chain partitioning
  • Richard Mycroft: Packing k-partite k-uniform hypergraphs
  • Roman Glebov, Yury Person and Wilma Weps: On Extremal Hypergraphs for Hamiltonian Cycles
  • Camino Balbuena and Julián Salas: New results on connectivity of cages
  • Anna Lladó: Almost every tree with n edges decomposes K2n,2n
  • Enno Buß, Hiệp Hàn and Mathias Schacht: Minimum vertex degree conditions for loose Hamilton cycles in 3-uniform hypergraphs
  • Antal Iványi and János Madarász: Perfect hypercubes
  • Marthe Bonamy, Matthew Johnson, Ioannis Lignos, Viresh Patel and Daniël Paulusma: On the diameter of reconfiguration graphs for vertex colourings
  • Robert Šamal: New approach to Petersen coloring
  • Nils Hebbinghaus and Anand Srivastav: Discrepancy of Centered Arithmetic Progressions in ℤp
  • Maria Axenovich and Lale Özkahya: On homometric sets in graphs
  • Elad Aigner-Horev, Reinhard Diestel and Luke Postle: Decomposing infinite matroids into their 3-connected minors
  • Hsun-Wen Chang and Siang-Ning Zeng: Enumeration of RNA Hairpins and Cloverleaves
  • Zoltán Király: Monochromatic components in edge-colored complete uniform hypergraphs
  • Alexander Sapozhenko: Upper bound for the number of perfect (n,3)-codes
  • Maksim Bashov: Minimal families in terms of double-sided shadow in the Boolean cube layer