The structural conjecture for nowhere dense classes without bounded expansion
The structural conjecture for nowhere dense classes without bounded expansion
Let be a monotone nowhere dense class of graphs. A -subdivision is obtained by replacing every edge of a graph by a path of length .
Structural conjecture for nowhere dense classes. If does not have bounded expansion, then there exists an integer such that includes -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.