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

00:00

Formale Metadaten

Titel
Coloring intersection graphs of L-figures in the plane
Serientitel
Anzahl der Teile
21
Autor
Lizenz
CC-Namensnennung - keine kommerzielle Nutzung - keine Bearbeitung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt in unveränderter Form zu jedem legalen und nicht-kommerziellen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

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