Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-6105
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.
URI: http://depositonce.tu-berlin.de/handle/11303/6664
http://dx.doi.org/10.14279/depositonce-6105
Issue Date: 2016
Date Available: 29-Aug-2017
DDC Class: 511 Mathematik
004 Informatik
Subject(s): on-line algorithm
graph coloring
bipartite graphs
Sponsor/Funder: DFG, GRK 1408, Methoden für diskrete Strukturen
Creative Commons License: https://creativecommons.org/licenses/by/4.0/
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:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 2 Mathematik und Naturwissenschaften » Institut für Mathematik » Fachgebiet Diskrete Mathematik » Publications

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


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.