pith. sign in

arxiv: 1702.07851 · v3 · pith:JJ4AJIJEnew · submitted 2017-02-25 · 🧮 math.CO

Chi-boundedness of graph classes excluding wheel vertex-minors

classification 🧮 math.CO
keywords graphsclassgraphhavingvertex-minorsboundedmathbbwheel
0
0 comments X
read the original abstract

A class of graphs is $\chi$-bounded if there exists a function $f:\mathbb N\rightarrow \mathbb N$ such that for every graph $G$ in the class and an 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 paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.