2019/01/21 by Lê Thành Dũng Nguyễn, Nguyên, Lê Thành Dũng
Computer Science · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Logic, programming, and type systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1901.07028
openalex publication_date 2019/01/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This note presents several results in graph theory inspired by the author's work in the proof theory of linear logic; these results are purely combinatorial and do not involve logic. We show that trails avoiding forbidden transitions, properly arc-colored directed trails and rainbow paths for complete multipartite color classes can be found in linear time, whereas finding rainbow paths is NP-complete for any other restriction on color classes. For the tractable cases, we also state new structural properties equivalent to Kotzig's theorem on the existence of bridges in unique perfect matchings. Another result on graphs equipped with unique perfect matchings that we prove here is the combinatorial counterpart of a theorem due to Bellin in linear logic: a connection between blossoms and bridge deletion orders.