Structural Properties of Graph Products
From MaRDI portal
Abstract: Dujmovi'{c}, Joret, Micek, Morin, Ueckerdt, and Wood [J. ACM 2020] established that every planar graph is a subgraph of the strong product of a graph with bounded treewidth and a path. Motivated by this result, this paper systematically studies various structural properties of cartesian, direct and strong products. In particular, we characterise when these graph products contain a given complete multipartite subgraph, determine tight bounds for their degeneracy, establish new lower bounds for the treewidth of cartesian and strong products, and characterise when they have bounded treewidth and when they have bounded pathwidth.
This page was built for publication: Structural Properties of Graph Products
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6379186)
