Title	Chi-boundedness of graph classes excluding wheel vertex-minors
Creator	Oum, Sang-il
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2017-08-21T15:50
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.
Extent	21 minutes
Subject	Mathematics; Combinatorics; Computer science; Discrete mathematics
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: KAIST
Series	BIRS Workshop Lecture Videos (Banff, Alta)
Date Available	2018-04-09
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0365256
URI	http://hdl.handle.net/2429/65184
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Faculty
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos