research
∙
08/05/2023
Independent dominating sets in planar triangulations
In 1996, Matheson and Tarjan proved that every near planar triangulation...
share
research
∙
01/20/2023
Separating the edges of a graph by a linear number of paths
Recently, Letzter proved that any graph of order n contains a collection...
research
∙
01/29/2021
Counting orientations of graphs with no strongly connected tournaments
Let S_k(n) be the maximum number of orientations of an n-vertex graph G ...
research
∙
12/09/2020
Decomposition of (2k+1)-regular graphs containing special spanning 2k-regular Cayley graphs into paths of length 2k+1
A P_ℓ-decomposition of a graph G is a set of paths with ℓ edges in G tha...
research
∙
05/27/2020
Counting graph orientations with no directed triangles
Alon and Yuster proved that the number of orientations of any n-vertex g...
research
∙
02/18/2020
On Tuza's conjecture for triangulations and graphs with small treewidth
Tuza (1981) conjectured that the size τ(G) of a minimum set of edges tha...
research
∙
11/11/2019
Towards Gallai's path decomposition conjecture
A path decomposition of a graph G is a collection of edge-disjoint paths...
research
∙
03/19/2018