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 | 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 | |