7 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_…
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 $…
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…