We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Chi-boundedness of graph classes excluding wheel vertex-minors

Formal Metadata

Title
Chi-boundedness of graph classes excluding wheel vertex-minors
Title of Series
Number of Parts
24
Author
Contributors
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
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.
Keywords