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
20 papers · 2 filters
Satisfying states of triangulations of a convex n-gon
Andrea Jiménez, Marcos Kiwi, Martin Loebl
In this work we count the number of satisfying states of triangulations of a convex n-gon using the transfer matrix method. We show an exponential (in n) lower bound. We also give…
Fractional total colourings of graphs of high girth
Tomas Kaiser, Andrew King, Daniel Kral
Reed conjectured that for every epsilon>0 and Delta there exists g such that the fractional total chromatic number of a graph with maximum degree Delta and girth at least g is at m…
Unexpected behaviour of crossing sequences
Matt DeVos, Bojan Mohar, Robert Samal
The n-th crossing number of a graph G, denoted cr_n(G), is the minimum number of crossings in a drawing of G on an orientable surface of genus n. We prove that for every a>b>0, the…
An enumeration of equilateral triangle dissections
Ales Drapal, Carlo Hamalainen
We enumerate all dissections of an equilateral triangle into smaller equilateral triangles up to size 20, where each triangle has integer side lengths. A perfect dissection has no…
The extremal function for partial bipartite tilings
Codrut Grosu, Jan Hladky
For a fixed bipartite graph H and given number c, 0<c<1, we determine the threshold T_H(c) which guarantees that any n-vertex graph with at edge density at least T_H(c) contains $(…
Homomorphism and embedding universal structures for restricted classes
Jan Hubička, Jaroslav Nešetřil
This paper unifies problems and results related to (embedding) universal and homomorphism universal structures. On the one side we give a new combinatorial proof of the existence o…
Non-representability of finite projective planes by convex sets
Martin Tancer
We prove that there is no d such that all finite projective planes can be represented by convex sets in R^d, answering a question of Alon, Kalai, Matousek, and Meshulam. Here, if P…
Short Cycle Covers of Cubic Graphs and Graphs with Minimum Degree Three
Tomas Kaiser, Daniel Kral, Bernard Lidicky +2
The Shortest Cycle Cover Conjecture of Alon and Tarsi asserts that the edges of every bridgeless graph with edges can be covered by cycles of total length at most …
Dualities and dual pairs in Heyting algebras
Jan Foniok, Jaroslav Nesetril, Ales Pultr +1
We extract the abstract core of finite homomorphism dualities using the techniques of Heyting algebras and (combinatorial) categories.
Latin bitrades, dissections of equilateral triangles and abelian groups
Ales Drapal, Carlo Hamalainen, Viteslav Kala
Let be a spherical latin bitrade. With each associate a set of linear equatio…
Domination number of cubic graphs with large girth
Daniel Kral, Petr Skoda, Jan Volec
We show that every n-vertex cubic graph with girth at least g have domination number at most 0.299871n+O(n/g)<3n/10+O(n/g).
Filling the gap between Turán's theorem and Pósa's conjecture
Peter Allen, Julia Böttcher, Jan Hladký
Much of extremal graph theory has concentrated either on finding very small subgraphs of a large graph (Turan-type results) or on finding spanning subgraphs (Dirac-type results). I…
An Eberhard-like theorem for pentagons and heptagons
Matt DeVos, Agelos Georgakopoulos, Bojan Mohar +1
Eberhard proved that for every sequence of non-negative integers satisfying Euler's formula , there are infinitely many…
Algebraic proof of Brooks' theorem
Jan Hladký, Daniel Král', Uwe Schauz
We give a proof of Brooks' theorem and its list coloring extension using the algebraic method of Alon and Tarsi; this also shows that the Brooks' theorem remains valid in a more ge…
Interleaved adjoints on directed graphs
Jan Foniok, Jaroslav Nesetril, Claude Tardif
For an integer k >= 1, the k-th interlacing adjoint of a digraph G is the digraph i_k(G) with vertex-set V(G)^k, and arcs ((u_1, ..., u_k), (v_1, ..., v_k)) such that (u_i,v_i) \in…
The tripartite Ramsey number for trees
Julia Böttcher, Jan Hladky, Diana Piguet
We prove that for all epsilon>0 there are c>0 and n_0 such that for all n>n_0 the following holds. For any two-colouring of the edges of one colour contains copies of a…
Graphs with bounded tree-width and large odd-girth are almost bipartite
Alexandr V. Kostochka, Daniel Kral', Jean-Sebastien Sereni +1
We prove that for every and every , there exists such that every graph with tree-width at most and odd-girth at least has circular chromatic number a…
Characterisations and Examples of Graph Classes with Bounded Expansion
Jaroslav Nešetřil, Patrice Ossona de Mendez, David R. Wood
Classes with bounded expansion, which generalise classes that exclude a topological minor, have recently been introduced by Nešetřil and Ossona de Mendez. These classes are defined…
An improved linear bound on the number of perfect matchings in cubic graphs
Louis Esperet, Daniel Kral, Petr Skoda +1
We show that every cubic bridgeless graph with n vertices has at least 3n/4-10 perfect matchings. This is the first bound that differs by more than a constant from the maximal dime…
Circular edge-colorings of cubic graphs with girth six
D. Král', E. Mácajová, J. Mazák +1
We show that the circular chromatic index of a (sub)cubic graph with girth at least six is at most 7/2.