The structural conjecture for nowhere dense classes without bounded expansion

Let C\mathcal C be a monotone nowhere dense class of graphs. A pp-subdivision is obtained by replacing every edge of a graph by a path of length p+1p+1.

Structural conjecture for nowhere dense classes. If C\mathcal C does not have bounded expansion, then there exists an integer pp such that C\mathcal C includes pp-subdivisions of graphs with arbitrarily large chromatic number and girth.

This conjecture would provide the structural input needed to extend the paper's characterization of first-order definable colorings from the proved cases to all hereditary addable topologically closed classes. Its status is presented as open in the paper.

Sources & referencesView supporting material

Primary source

Jaroslav Nesetril and Patrice Ossona De Mendez, “On First-Order Definable Colorings”, arXiv:1403.1995 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.