Отображение сетевого контента Отображение сетевого контента

Skip banner

Навигационная цепочка Навигационная цепочка

Навигация Навигация

Отображение сетевого контента Отображение сетевого контента

Informatyka Teoretyczna

Organizers: Paweł Idziak
Usual time and place: środa, 16:15-18:00, sala 1094
site-www: tcs.uj.edu.pl/tcs
event-date: 27.10.2010
Speaker: Grzegorz Matecki
Title of the talk: First-Fit coloring of co-comparability graphs
Abstract:

One of the simplest heuristics to obtain a proper coloring of a graph is First-Fit algorithm. First-Fit visits each vertex of a graph in the already given order and assigns to it the smallest possible number (color) such that two vertices connected by an edge are not monochromatic. The class of 2-colorable co-comparability graphs is known to be infinitely colorable by First-Fit. We proved that H-free co-comparability graphs with a fixed chromatic number are finitely colorable by First-Fit if and only if H is a 2-colorable co-comparability graph. It provides the full characterization of First-Fit on co-comparability graphs in terms of forbidden structures.<br />This is a joint work with Bartłomiej Bosek and Tomasz Krawczyk.

Отображение сетевого контента Отображение сетевого контента