Triangulating Almost-Complete Graphs

MaRDI QIDQ6280775zbMATH OpenFDO

Authors Kim Nguyen Pham, Landon Settle, Kayla Wright, Padraic Bartlett

Publication date 13 December 2016

Mathematics Subject Classification ID

Combinatorics (05-XX)

Abstract: A triangle decomposition of a graph $G$ is a partition of the edges of $G$ into triangles. Two necessary conditions for $G$ to admit such a decomposition are that $|E(G)|$ is a multiple of three and that the degree of any vertex in $G$ is even; we call such graphs tridivisible. Kirkman's work on Steiner triple systems established that for $Gsimeq{K}_n$, $G$ admits a triangle decomposition precisely when $G$ is tridivisible. In 1970, Nash-Williams conjectured that tridivisiblity is also sufficient for "almost-complete" graphs, which for this talk's purposes we interpret as any graph $G$ on $n$ vertices with $$ for some appropriately small constants $epsilon,xi$. Nash-Williams conjectured that $epsilon=xi=1/4$ would suffice; in 1991, Gustavsson demonstrated in his dissertation that $epsilon=xi<10^{-24}$ suffices for all $nequiv3,9mod18$, and in 2015 Keevash's work on the existence conjecture for combinatorial designs established that some value of $epsilon$ existed for any $n$. In this paper, we prove that for any $epsilon<frac1432$, there is a constant $xi$ such that any $G$ with $delta(G)geq(1-epsilon)n$ and $$ admits such a decomposition, and offer an algorithm that explicitly constructs such a triangulation. Moreover, we note that our algorithm runs in polynomial time on such graphs. (This last observation contrasts with Holyer's result that finding triangle decompositions in general is a NP-complete problem.)

This page was built for publication: Triangulating Almost-Complete Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6280775)