2016/11/28 by Ali, Niran Abbas, Chia, Gek L., Trao, Hazim Michman +1 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1611.09033
Motivated by a result of [1] which states that if F is a subgraph of a convex complete graph Kn and F contains no boundary edge of Kn and |E(F)| ≤ n-3, then Kn - F admits a triangulation, we determine necessary and sufficient conditions on F with |E(F)| ≤ n-1 for which the conclusion remains true. For |E(F)| ≥ n, we investigate the possibility of packing F in Kn such that Kn -F admits a triangulation for certain families of graphs F. These results are then applied to determine the convex skewness of the convex graphs of the form Kn - F.