10.9k citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- Centre National de la Recherche ScientifiqueFR3.6k papers
- Institut National de Physique Nucléaire et de Physique des ParticulesFR3.2k papers
- Commissariat à l'Énergie Atomique et aux Énergies AlternativesFR3k papers
- Joint Institute for Nuclear ResearchRU2.7k papers
- Institute for High Energy PhysicsES2.7k papers
- European Organization for Nuclear ResearchCH2.6k papers
- Institut de Recherche sur les Lois Fondamentales de l'UniversFR2.6k papers
- Institute of High Energy PhysicsCN2.6k papers
- Rutherford Appleton LaboratoryGB2.5k papers
- Deutsches Elektronen-Synchrotron DESYDE2.5k papers
- National and Kapodistrian University of AthensGR2.5k papers
- Istituto Nazionale di Fisica Nucleare, Sezione di NapoliIT2.4k papers
26 papers · 2 filters
On the bend-number of planar and outerplanar graphs
Daniel Heldt, Kolja Knauer, Torsten Ueckerdt
The bend-number b(G) of a graph G is the minimum k such that G may be represented as the edge intersection graph of a set of grid paths with at most k bends. We confirm a conjectur…
Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns
Anders Claesson, Vít Jelínek, Einar Steingrímsson
We prove that the Stanley-Wilf limit of any layered permutation pattern of length is at most , and that the Stanley-Wilf limit of the pattern 1324 is at most 16. Th…
On empty pentagons and hexagons in planar point sets
Pavel Valtr
We give improved lower bounds on the minimum number of -holes (empty convex -gons) in a set of points in general position in the plane, for .
Embedding spanning bipartite graphs of small bandwidth
Fiachra Knox, Andrew Treglown
Boettcher, Schacht and Taraz gave a condition on the minimum degree of a graph G on n vertices that ensures G contains every r-chromatic graph H on n vertices of bounded degree and…
List colorings with distinct list sizes, the case of complete bipartite graphs
Zoltán Füredi, Ida Kantor
Let be a function on the vertex set of the graph . The graph is {\em -choosable} if for every collection of lists with list sizes speci…
On discrete field theory properties of the dimer and Ising models and their conformal field theory limits
Igor Kriz, Martin Loebl, Petr Somberg
We study various mathematical aspects of discrete models on graphs, specifically the Dimer and the Ising models. We focus on proving gluing formulas for individual summands of the…
Constant-factor approximation of domination number in sparse graphs
Zdenek Dvorak
The k-domination number of a graph is the minimum size of a set X such that every vertex of G is in distance at most k from X. We give a linear time constant-factor approximation a…
Non-degenerated groundstates in the antiferromagnetic Ising model on triangulations
Andrea Jiménez
A triangulation is an embedding of a graph into a closed Riemann surface so that each face boundary is a 3-cycle of the graph. In this work, groundstate degeneracy in the antiferro…
On perfect packings in dense graphs
József Balogh, Alexandr V. Kostochka, Andrew Treglown
We say that a graph G has a perfect H-packing if there exists a set of vertex-disjoint copies of H which cover all the vertices in G. We consider various problems concerning perfec…
Highly arc-transitive digraphs -- counterexamples and structure
Matt DeVos, Bojan Mohar, Robert Šámal
We resolve two problems of [Cameron, Praeger, and Wormald -- Infinite highly arc transitive digraphs and universal covering digraphs, Combinatorica 1993]. First, we construct a loc…
Pairs of heavy subgraphs for Hamiltonicity of 2-connected graphs
Binlong Li, Zdeněk Ryjáček, Ying Wang +1
Let be a graph on vertices. An induced subgraph of is called heavy if there exist two nonadjacent vertices in with degree sum at least in . We say that $…
Choosability of planar graphs of girth 5
Zdenek Dvorak, Ken-ichi Kawarabayashi
Thomassen proved that any plane graph of girth 5 is list-colorable from any list assignment such that all vertices have lists of size two or three and the vertices with list of siz…
Min-max relations for odd cycles in planar graphs
Daniel Kral, Jean-Sebastien Sereni, Ladislav Stacho
Let m(G) be the maximum number of vertex-disjoint odd cycles of a graph G and t(G) the minimum number of vertices whose removal makes G bipartite. We show that t(G)<=6m(G) if G is…
Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
Frantisek Kardos, Daniel Kral, Jan Volec
We show that for every cubic graph G with sufficiently large girth there exists a probability distribution on edge-cuts of G such that each edge is in a randomly chosen cut with pr…
A new lower bound based on Gromov's method of selecting heavily covered points
Daniel Kral, Lukas Mach, Jean-Sebastien Sereni
Boros and Furedi (for d=2) and Barany (for abritrary d) proved that there exists a positive real number c_d such that for every set P of n points in R^d in general position, there…
d-Representability of simplicial complexes of fixed dimension
Martin Tancer
Let K be a simplicial complex with vertex set V = {v_1,..., v_n}. The complex K is d-representable if there is a collection {C_1,...,C_n} of convex sets in R^d such that a subcolle…
On the connectivity of visibility graphs
Michael S. Payne, Attila Pór, Pavel Valtr +1
The visibility graph of a finite set of points in the plane has the points as vertices and an edge between two vertices if the line segment between them contains no other points. T…
Counting Self-Dual Interval Orders
Vít Jelínek
In this paper, we present a new method to derive formulas for the generating functions of interval orders, counted with respect to their size, magnitude, and number of minimal and…
Bipartizing fullerenes
Zdenek Dvorak, Bernard Lidicky, Riste Skrekovski
A fullerene graph is a cubic bridgeless planar graph with twelve 5-faces such that all other faces are 6-faces. We show that any fullerene graph on n vertices can be bipartized by…
On the Removal Lemma for Linear Systems over Abelian Groups
Daniel Král', Oriol Serra, Lluís Vena
In this paper we present an extension of the removal lemma to integer linear systems over abelian groups. We prove that, if the --determinantal of an integer matri…
Non-three-colorable common graphs exist
Hamed Hatami, Jan Hladky, Daniel Kral +2
A graph H is called common if the total number of copies of H in every graph and its complement asymptotically minimizes for random graphs. A former conjecture of Burr and Rosta, e…
Tight bounds on the maximum size of a set of permutations with bounded VC-dimension
Josef Cibulka, Jan Kyncl
The VC-dimension of a family P of n-permutations is the largest integer k such that the set of restrictions of the permutations in P on some k-tuple of positions is the set of all…
Graphs with two crossings are 5-choosable
Zdeněk Dvořák, Bernard Lidický, Riste Škrekovski
A graph G is k-choosable if G can be properly colored whenever every vertex has a list of at least k available colors. Thomassen's theorem states that every planar graph is 5-choos…
Simple Proofs of Classical Theorems in Discrete Geometry via the Guth--Katz Polynomial Partitioning Technique
Haim Kaplan, Jiří Matoušek, Micha Sharir
Recently Guth and Katz \cite{GK2} invented, as a step in their nearly complete solution of Erdős's distinct distances problem, a new method for partitioning finite point sets in $\…