A prime factor theorem for bipartite graphs. (July 2015)

• Record Type: Journal Article
• Authors: Hammack, Richard; Puffenberger, Owen
• Is Part Of: European journal of combinatorics. Volume 47(2015:Jul.)
• Page Start: 123
• Page End: 140
• Publication Date: 2015-07
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2015.02.003
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: It has long been known that the class of connected nonbipartite graphs (with loops allowed) obeys unique prime factorization over the direct product of graphs. Moreover, it is known that prime factorization is not necessarily unique in the class of connected bipartite graphs. But any prime factorization of a connected bipartite graph has exactly one bipartite factor. It has become folklore in some circles that this prime bipartite factor must be unique among all factorings, but until now this conjecture has withstood proof. This paper presents a proof. We show that if a connected bipartite graph G has two factorings G ≅ A × B and G ≅ A ′ × B ′, where B and B ′ are prime and bipartite, then B ≅ B ′ .