Open Collections

Description

A class of graphs is \(\chi\)-bounded if there exists a function \(f:\mathbb{N}→\mathbb{N}\) such that for every graph \(G\) in the class and every induced subgraph \(H\) of \(G\), if \(H\) has no clique of size \(q+1\), then the chromatic number of \(H\) is less than or equal to \(f(q)\). We denote by \(W_n\) the wheel graph on \(n+1\) vertices. We show that the class of graphs having no vertex-minor isomorphic to \(W_n\) is \(\chi\)-bounded. This generalizes several previous results; \(\chi\)-boundedness for circle graphs, for graphs having no \(W_5\) vertex-minors, and for graphs having no fan vertex-minors. This is joint work with Hojin Choi, O-joung Kwon, and Paul Wollan.