{"id":"palomar/PALOMAR-2026-09-14-000005","url":"https://github.com/shaikidris/gallai-bowtie-removal/tree/2f19c6ff50ec0a7cb0d979f33870378299d78fea","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-09-14-000005-v1.json","repo":"https://github.com/shaikidris/gallai-bowtie-removal","tags":["math.CO","msc:05C38","msc:05C70","graph-theory","path-decomposition","gallai-conjecture"],"score":0,"title":"Gallai’s Path Decomposition Conjecture for Graphs with Small Bowtie Boundaries","trust":"high","domain":"math.CO","source":"palomar","authors":["Idris Ali Shaik"],"reviews":0,"subject":"math.CO","summary":"We prove sufficient conditions for partitioning the edges of a connected finite simple graph into at most ⌈|V(G)|/2⌉ simple paths. The results concern bowtie components—two triangles sharing exactly one vertex—in the subgraph induced by even-degree vertices. They include removal preserving specified endpoints, a sharp full-incidence star expansion, composition under explicit boundary hypotheses, and corollaries for graphs with two bowtie components. The unrestricted two-exception conjecture remains open.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-09-14","reactions":{},"formalized":true,"formalizes":[{"title":"Gallai’s Path Decomposition Conjecture for Graphs with Small Bowtie Boundaries","identifier":"","relationship":"formalizes"},{"title":"Gallai's Conjecture on Path Decompositions","identifier":"doi:10.1007/s40305-022-00435-3","relationship":"formalizes"},{"title":"Towards Gallai's path decomposition conjecture","identifier":"https://arxiv.org/abs/1911.04546","relationship":"formalizes"}]}