TY - JOUR
T1 - Structural properties of graph products
AU - Hickingbotham, Robert
AU - Wood, David R.
N1 - Funding Information:
Research supported by an Australian Government Research Training Program Scholarship. Research supported by the Australian Research Council. Open access publishing facilitated by Monash University, as part of the Wiley ‐ Monash University agreement via the Council of Australian University Librarians.
Publisher Copyright:
© 2023 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.
PY - 2023/8/9
Y1 - 2023/8/9
N2 - Dujmovć, Joret, Micek, Morin, Ueckerdt, and Wood 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.
AB - Dujmovć, Joret, Micek, Morin, Ueckerdt, and Wood 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.
KW - degeneracy
KW - graph products
KW - treewidth
UR - http://www.scopus.com/inward/record.url?scp=85167357158&partnerID=8YFLogxK
U2 - 10.1002/jgt.23023
DO - 10.1002/jgt.23023
M3 - Article
AN - SCOPUS:85167357158
SN - 0364-9024
JO - Journal of Graph Theory
JF - Journal of Graph Theory
ER -