Charles University

output

19922026

most citedObservation of a new particle in the search for the Standard Model Higgs boson with the ATLAS detector at the LHC

10.9k citations

researchers with a paper here

Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.

collaborating institutions

Showing 2014 · math.COShow all

12 papers · 2 filters

math.CO2014★ 42 cited

On Low Tree-Depth Decompositions

Jaroslav Nesetril, Patrice Ossona De Mendez

The theory of sparse structures usually uses tree like structures as building blocks. In the context of sparse/dense dichotomy this role is played by graphs with bounded tree depth…

math.CO2014★ 35 cited

Minimum number of monotone subsequences of length 4 in permutations

József Balogh, Ping Hu, Bernard Lidický +3

We show that for every sufficiently large $n$ , the number of monotone subsequences of length four in a permutation on $n$ points is at least $\binom{\lfloor n/3 \rfloor}{4} + \bino…

math.CO2014★ 4 cited

Distributive and anti-distributive Mendelsohn triple systems

Diane M. Donovan, Terry S. Griggs, Thomas A. McCourt +2

We prove that the existence spectrum of Mendelsohn triple systems whose associated quasigroups satisfy distributivity corresponds to the Loeschian numbers, and provide some enumera…

math.CO2014★ 7 cited

Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs

Roman Čada, Binlong Li, Bo Ning +1

A graph is called \emph{claw-free} if it contains no induced subgraph isomorphic to $K_{1, 3}$ . Matthews and Sumner proved that a 2-connected claw-free graph $G$ is hamiltonian if e…

math.CO2014★ 11 cited

Automorphism Groups of Geometrically Represented Graphs

Pavel Klavík, Peter Zeman

We describe a technique to determine the automorphism group of a geometrically represented graph, by understanding the structure of the induced action on all geometric representati…

math.CO2014★ 2 cited

Restricted frame graphs and a conjecture of Scott

Jérémie Chalopin, Louis Esperet, Zhentao Li +1

Scott proved in 1997 that for any tree $T$ , every graph with bounded clique number which does not contain any subdivision of $T$ as an induced subgraph has bounded chromatic number…

math.CO2014★ 7 cited

Strongly polynomial sequences as interpretations

Andrew Goodall, Jaroslav Nesetril, Patrice Ossona de Mendez

A strongly polynomial sequence of graphs $(G_{n})$ is a sequence $(G_{n})_{n \in N}$ of finite graphs such that, for every graph $F$ , the number of homomorphisms from $F$ to $G_…

math.CO2014★ 9 cited

Infinite dimensional finitely forcible graphon

Roman Glebov, Tereza Klimosova, Daniel Kral

Graphons are analytic objects associated with convergent sequences of dense graphs. Finitely forcible graphons, i.e., those determined by finitely many subgraph densities, are of p…

math.CO2014

Fractional coloring of triangle-free planar graphs

Zdeněk Dvořák, Jean-Sébastien Sereni, Jan Volec

We prove that every planar triangle-free graph on $n$ vertices has fractional chromatic number at most $3 - \frac{1}{n + 1/3}$ .

math.CO2014

A note on circular chromatic number of graphs with large girth and similar problems

Jaroslav Nesetril, Patrice Ossona De Mendez

In this short note, we extend the result of Galluccio, Goddyn, and Hell, which states that graphs of large girth excluding a minor are nearly bipartite. We also prove a similar res…

math.CO2014

Universality of intervals of line graph order

Jiří Fiala, Jan Hubička, Yangjing Long

We prove that for every $d \geq 3$ the homomorphism order of the class of line graphs of finite graphs with maximal degree $d$ is universal. This means that every finite or countabl…

math.CO2014★ 18 cited

Bowtie-free graphs have a Ramsey lift

Jan Hubička, Jaroslav Nešetřil

A bowtie is a graph consisting of two triangles with one vertex identified. We show that the class of all (countable) graphs not containing a bowtie as a subgraph has a Ramsey lift…