Please use this identifier to cite or link to this item:
Main Title: An On-line competitive algorithm for coloring bipartite graphs without long induced paths
Author(s): Micek, Piotr
Wiechert, Veit
Type: Article
Language Code: en
Abstract: The existence of an on-line competitive algorithm for coloring bipartite graphs is a tantalizing open problem. So far there are only partial positive results for bipartite graphs with certain small forbidden graphs as induced subgraphs. We propose an on-line competitive coloring algorithm for P9-free bipartite graphs.
Issue Date: 2016
Date Available: 29-Aug-2017
DDC Class: 511 Allgemeine mathematische Prinzipien
004 Datenverarbeitung; Informatik
510 Mathematik
Subject(s): on-line algorithm
graph coloring
bipartite graphs
Sponsor/Funder: DFG, GRK 1408, Methoden für diskrete Strukturen
Journal Title: Algorithmica
Publisher: Springer
Publisher Place: New York, NY
Volume: 77
Issue: 4
Publisher DOI: 10.1007/s00453-016-0130-2
Page Start: 1060
Page End: 1070
EISSN: 1432-0541
ISSN: 0178-4617
Appears in Collections:FG Diskrete Mathematik » Publications

Files in This Item:
File Description SizeFormat 
10.1007_s00453-016-0130-2.pdf513.29 kBAdobe PDFThumbnail

This item is licensed under a Creative Commons License Creative Commons