Chi-boundedness of graph classes excluding wheel vertex-minors
In: 17w5154: Geometric and Structural Graph Theory; BIRS Workshop Lecture Videos (Banff, Alta); (2017)
Online
videoRecording
Zugriff:
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. ; Non UBC ; Unreviewed ; Author affiliation: KAIST ; Faculty
Titel: |
Chi-boundedness of graph classes excluding wheel vertex-minors
|
---|---|
Autor/in / Beteiligte Person: | Oum, Sang-il |
Link: | |
Quelle: | 17w5154: Geometric and Structural Graph Theory; BIRS Workshop Lecture Videos (Banff, Alta); (2017) |
Veröffentlichung: | Banff International Research Station for Mathematical Innovation and Discovery, 2017 |
Medientyp: | videoRecording |
Schlagwort: |
|
Sonstiges: |
|