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

Coloring intersection graphs of L-figures in the plane

Formal Metadata

Title
Coloring intersection graphs of L-figures in the plane
Title of Series
Number of Parts
21
Author
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
Pawlik et al. (2013) proved that a particular family of triangle-free graphs with chromatic number Θ(loglogn) (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(loglogn). This improves the previous bound of O(logn) (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.