We show that any two cartesian factorizations of a connected graph have a strict common refinement, improving on the unique factorization theorem of G. Sabidussi. (The cartesian product is the product wherein two vertices are adjacent when they are adjacent in one coordinate and equal in all other coordinates.) Among the applications, we can deduce the strict refinement theorem for chain-finite posets, and (using a cartesian factorization algorithm of P. Winkler) we give polynomial-time algorithm for cardinal factorization of connected finite posets.
- scientific article; zbMATH DE number 1332355
- On strict (outer-)confluent graphs
- On strict (outer-)confluent graphs
- Refined finiteness and degree properties in graphs
- On strict-double-bound numbers of graphs and graph operations
- Note on strict-double-bound graphs and numbers
- On strict semibound graphs of posets
- Strict optimal rubbling of graphs
- scientific article; zbMATH DE number 6181702
- A refinement of choosability of graphs
- A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
- Automorphisms and products of ordered sets
- Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time
- Factoring a graph in polynomial time
- Graph multiplication
- scientific article; zbMATH DE number 3834029 (Why is no real title available?)
- scientific article; zbMATH DE number 3889587 (Why is no real title available?)
- scientific article; zbMATH DE number 3786842 (Why is no real title available?)
- On direct product desomposition of partially ordered sets
- On Isometric Embeddings of Graphs
- Refinement properties for relational structures
- Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time
- Products of abstract polytopes
- \(\mathcal{M}\)-coextensive objects and the strict refinement property
- Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time
- scientific article; zbMATH DE number 1332355 (Why is no real title available?)
- Groups for which it is easy to detect graphical regular representations
- Digraphs with small automorphism groups that are Cayley on two nonisomorphic groups
- The semigroup of metric measure spaces and its infinitely divisible probability measures
- Finding the prime factors of strong direct product graphs in polynomial time
This page was built for publication: Strict refinement for graphs and digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1072575)
