Testing subdivision-freeness: property testing meets structural graph theory

DOI10.1145/2488608.2488663MaRDI QIDQ5495814zbMATH OpenOpenAlexFDO

Authors Ken-ichi Kawarabayashi, Yuichi Yoshida

Publication date 7 August 2014

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2488608.2488663

Mathematics Subject Classification ID

Vertex degrees (05C07) Structural characterization of families of graphs (05C75) Graph minors (05C83)

Recommendations

• The subgraph testing model
• Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty
• The subgraph testing model
• Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
• On testable properties in bounded degree graphs

Cited in

(5)

• On the tree-width of even-hole-free graphs
• scientific article; zbMATH DE number 6469238 (Why is no real title available?)
• An explicit construction of graphs of bounded degree that are far from being Hamiltonian
• On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing
• Testing some first-order logic properties on sparse graphs

This page was built for publication: Testing subdivision-freeness: property testing meets structural graph theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495814)