Clustered coloring of (path+2K1)-free graphs on surfaces

Esperet and Joret proved that planar graphs with bounded maximum degree are 3-colorable with bounded clustering. Liu and Wood asked whether the conclusion holds with the assumption of the bounded maximum degree replaced by assuming that no two vertices have many common neighbors. We answer this question in positive, in the following stronger form: Let P'' t be the complete join of two isolated vertices with a path on t vertices. For any surface Sigma, a subgraph-closed class of graphs drawn on Sigma is 3-choosable with bounded clustering if and only if there exists t such that Pt'' does not belong to the class. (c) 2025 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.