![](/files/happy5.png)
Are vertex minor closed classes chi-bounded?
Question Is every proper vertex-minor closed class of graphs chi-bounded?
We say that a family of graphs is
-bounded if there is a function
so that
for every
.
If is a simple graph, a vertex minor of
is any graph which can be obtained by a sequence of the following operations:
- \item delete a vertex \item choose a vertex
![$ v $](/files/tex/96cbd9a16c6a5eab03815b093b08f3b2db614e9a.png)
![$ v $](/files/tex/96cbd9a16c6a5eab03815b093b08f3b2db614e9a.png)
![$ u,w $](/files/tex/dc48e43731fc0217dbc437c3cca8b50096eb7969.png)
![$ v $](/files/tex/96cbd9a16c6a5eab03815b093b08f3b2db614e9a.png)
![$ u,w $](/files/tex/dc48e43731fc0217dbc437c3cca8b50096eb7969.png)
Dvorak and Kral [DK] showed that this conjecture is true for class of graphs of bounded rank-width, and the class of graphs having no vertex-minor isomorphic to the wheel on
vertices.
Bibliography
[DK] Z. Dvorak and D. Král. Classes of graphs with small rank decompositions are χ-bounded. European J. Combin., 33(4):679–-683, 2012. MathSciNet
* indicates original appearance(s) of problem.