Geelen's chi-boundedness conjecture for graphs excluding a vertex-minor

Let HH be a graph. A class of graphs is χ\chi-bounded if there exists a function f:NNf:\mathbb N\rightarrow\mathbb N such that for every graph GG in the class and every induced subgraph JJ of GG, χ(J)f(ω(J))\chi(J)\leq f(\omega(J)), where χ(J)\chi(J) and ω(J)\omega(J) denote the chromatic and clique numbers of JJ, respectively. A vertex-minor of a graph is an induced subgraph of a graph obtained by a sequence of local complementations. Geelen's conjecture. For every graph HH, the class of graphs with no HH vertex-minor is χ\chi-bounded. This conjecture extends known χ\chi-boundedness results for circle graphs and graphs of bounded rank-width; its general case remains open.

Sources & referencesView supporting material

Primary source

Hojin Choi, O-joung Kwon, Sang-il Oum and Paul Wollan, “Chi-boundedness of graph classes excluding wheel vertex-minors”, arXiv:1702.07851 (2018).

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.