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
17 papers · 2 filters
The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree
Vít Jelínek, Eva Jelínková, Jan Kratochvíl +3
It is known that every planar graph has a planar embedding where edges are represented by non-crossing straight-line segments. We study the planar slope number, i.e., the minimum n…
Exponentially many perfect matchings in cubic graphs
Louis Esperet, Frantisek Kardos, Andrew King +2
We show that every cubic bridgeless graph G has at least 2^(|V(G)|/3656) perfect matchings. This confirms an old conjecture of Lovasz and Plummer. This version of the paper uses a…
Segment representation of a subclass of co-planar graphs
Mathew C. Francis, Jan Kratochvíl, Tomáš Vyskočil
A graph is said to be a segment graph if its vertices can be mapped to line segments in the plane such that two vertices have an edge between them if and only if their correspondin…
Star chromatic index
Zdeněk Dvořák, Bojan Mohar, Robert Šámal
The star chromatic index of a graph is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi-colo…
Ramsey-type constructions for arrangements of segments
Jan Kynčl
Improving a result of Károlyi, Pach and Tóth, we construct an arrangement of segments in the plane with at most pairwise crossing or pairwise disjoint…
Packing six T-joins in plane graphs
Zdenek Dvorak, Ken-ichi Kawarabayashi, Daniel Kral
Let G be a plane graph and T an even subset of its vertices. It has been conjectured that if all T-cuts of G have the same parity and the size of every T-cut is at least k, then G…
A counterexample to Wegner's conjecture on good covers
Martin Tancer
In 1975 Wegner conjectured that the nerve of every finite good cover in R^d is d-collapsible. We disprove this conjecture. A good cover is a collection of open sets in R^d such tha…
Geometric representations of linear codes
Pavel Rytíř
We say that a linear code C over a field F is triangular representable if there exists a two dimensional simplicial complex such that C is a punctured code of the kernel ker $Δ…
Multi-latin squares
Nicholas Cavenagh, Carlo Hamalainen, James G. Lefevre +1
A multi-latin square of order and index is an array of multisets, each of cardinality , such that each symbol from a fixed set of size occurs times i…
The number of unit distances is almost linear for most norms
Jiří Matoušek
We prove that there exists a norm in the plane under which no n-point set determines more than O(n log n log log n) unit distances. Actually, most norms have this property, in the…
On the nonexistence of k-reptile tetrahedra
Jiří Matoušek, Zuzana Safernová
A d-dimensional simplex S is called a k-reptile if it can be tiled without overlaps by simplices S_1,S_2,...,S_k that are all congruent and similar to S. For d=2, k-reptile simplic…
Pattern avoidance in partial permutations
Anders Claesson, Vit Jelinek, Eva Jelinkova +1
Motivated by the concept of partial words, we introduce an analogous concept of partial permutations. A partial permutation of length n with k holes is a sequence of symbols $π= π_…
Spanning trees of 3-uniform hypergraphs
Andrew Goodall, Anna de Mier
Masbaum and Vaintrob's "Pfaffian matrix tree theorem" implies that counting spanning trees of a 3-uniform hypergraph (abbreviated to 3-graph) can be done in polynomial time for a c…
A superlinear bound on the number of perfect matchings in cubic bridgeless graphs
L. Esperet, F. Kardos, D. Kral'
Lovasz and Plummer conjectured in the 1970's that cubic bridgeless graphs have exponentially many perfect matchings. This conjecture has been verified for bipartite graphs by Voorh…
Some examples of universal and generic partial orders
Jaroslav Nesetril, Jan Hubicka
We survey structures endowed with natural partial orderings and prove their universality. These partial orders include partial orders on sets of words, partial orders formed by geo…
Maltsev digraphs have a majority polymorphism
Alexandr Kazda
We prove that when a digraph has a Maltsev polymorphism, then also has a majority polymorphism. We consider the consequences of this result for the structure of Maltsev gra…
On the computational complexity of degenerate unit distance representations of graphs
Jan Kratochvil, Boris Horvat, Tomaz Pisanski
Some graphs admit drawings in the Euclidean k-space in such a (natu- ral) way, that edges are represented as line segments of unit length. Such drawings will be called k dimensiona…