1 citations · 1 across the 9 of their papers we have counts for
9 papers
Crossing tournaments are polynomially -bounded
Lila Crew, Xinyue Fan, Hidde Koerts +2
Given a tournament , Aboulker, Aubian, Charbit, and Lopes (2023) defined its clique number as the minimum clique number of a backedge graph of , and raised the que…
Decomposing tournaments into comparability graphs
Pierre Aboulker, Logan Crew, Julien Duron +7
In this note, we introduce the \emph{partial order decomposition number} of a digraph , denoted , defined as the minimum integer such that $A(D)=A(P_1)\cup\cdots\cup…
Homomorphism counting for immersion-closed classes is not isomorphism
Andrea Jiménez, Benjamin Moore, Daniel A. Quiroz +1
Lovász proved that two graphs and are isomorphic if for all graphs , where denotes the number of homomorphisms from to $G_2…
Characterizing Large Clique Number in Tournaments
Logan Crew, Xinyue Fan, Hidde Koerts +2
Aboulker, Aubian, Charbit, and Lopes (2023) defined the clique number of a tournament to be the minimum clique number of one of its backedge graphs. Here we show that if is a t…
Flow-critical graphs
Arnbjörg Soffía Árnadóttir, Zdeněk Dvořák, Bernard Lidický +3
Lovász et al. proved that every -edge-connected graph has a nowhere-zero -flow. In fact, they proved a more technical statement which says that there exists a nowhere zero $3…
Smoothed analysis for graph isomorphism
Michael Anastos, Matthew Kwan, Benjamin Moore
There is no known polynomial-time algorithm for graph isomorphism testing, but elementary combinatorial "refinement" algorithms seem to be very efficient in practice. Some philosop…
An Approximate Version of the Strong Nine Dragon Tree Conjecture
Sebastian Mies, Benjamin Moore
We prove the Strong Nine Dragon Tree Conjecture is true if we replace the edge bound with $d + \big\lceil k \big\lfloor\frac{d-1}{k+1}\big\rfloor \big(\frac{d}{k+1} - \frac{1}{2} \…
The Strong Nine Dragon Tree Conjecture is True for
Sebastian Mies, Benjamin Moore
The arboricity of an undirected graph is the minimal number such that can be partitioned into forests on . Nash-Williams' formula states that $k =…
Beyond the Pseudoforest Strong Nine Dragon Tree Theorem
Sebastian Mies, Benjamin Moore, Evelyne Smith-Roberge
The pseudoforest version of the Strong Nine Dragon Tree Conjecture states that if a graph has maximum average degree …