Title	Coloring intersection graphs of L-figures in the plane
Creator	Walczak, Bartosz
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2018-02-08T14:43
Description	Pawlik et al. (2013) proved that a particular family of triangle-free graphs with chromatic number $\Theta(\log\log n)$ (where $n$ is the number of vertices) can be represented as intersection graphs of L-figures in the plane. I will sketch a proof of the matching upper bound: all triangle-free intersection graphs of L-figures have chromatic number $O(\log\log n)$. This improves the previous bound of $O(\log n)$ (McGuinness, 1996) and is a little step towards obtaining analogous improvements for more general and better known classes of geometric intersection graphs, such as segment graphs and general string graphs.
Extent	35 minutes
Subject	Mathematics; Convex and discrete geometry; Combinatorics
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: Jagiellonian University
Series	BIRS Workshop Lecture Videos (Banff, Alta)
Date Available	2018-08-08
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0369743
URI	http://hdl.handle.net/2429/66699
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