An On-line Competitive Algorithm for Coloring Bipartite Graphs Without Long Induced Paths

被引：0
|
作者：
Piotr Micek
Veit Wiechert
机构：
[1] Jagiellonian University,Theoretical Computer Science Department, Faculty of Mathematics and Computer Science
[2] Technische Universität Berlin,Institut für Mathematik
来源：
Algorithmica | 2017年 / 77卷
关键词：
On-line algorithm; Graph coloring; Bipartite graphs; 05C15; 05C85; 68R10;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_9$$\end{document}-free bipartite graphs.
引用
收藏
页码：1060 / 1070
页数：10
相关论文
共 13 条
  • [1] An On-line Competitive Algorithm for Coloring Bipartite Graphs Without Long Induced Paths
    Micek, Piotr
    Wiechert, Veit
    ALGORITHMICA, 2017, 77 (04) : 1060 - 1070
  • [2] Approximately Coloring Graphs Without Long Induced Paths
    Maria Chudnovsky
    Oliver Schaudt
    Sophie Spirkl
    Maya Stein
    Mingxian Zhong
    Algorithmica, 2019, 81 : 3186 - 3199
  • [3] Approximately Coloring Graphs Without Long Induced Paths
    Chudnovsky, Maria
    Schaudt, Oliver
    Spirkl, Sophie
    Stein, Maya
    Zhong, Mingxian
    ALGORITHMICA, 2019, 81 (08) : 3186 - 3199
  • [4] Coloring graphs without short cycles and long induced paths
    Golovach, Petr A.
    Paulusma, Daniel
    Song, Jian
    DISCRETE APPLIED MATHEMATICS, 2014, 167 : 107 - 120
  • [5] On the complexity of 4-coloring graphs without long induced paths
    Le, Van Bang
    Randerath, Bert
    Schiermeyer, Ingo
    THEORETICAL COMPUTER SCIENCE, 2007, 389 (1-2) : 330 - 335
  • [6] On-line edge-coloring algorithms for degree-bounded bipartite graphs
    Taki, M
    Sugiura, M
    Kashiwabara, T
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2002, E85A (05): : 1062 - 1065
  • [7] Obstructions for three-coloring graphs without induced paths on six vertices
    Chudnovsky, Maria
    Goedgebeur, Jan
    Schaudt, Oliver
    Zhong, Mingxian
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2020, 140 : 45 - 83
  • [8] On the on-line coloring of unit interval graphs with proper interval representation
    Curbelo, Israel R.
    Malko, Hannah R.
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2025, 27 (02)
  • [9] A coloring algorithm for 4K1-free line graphs
    Fraser, Dallas J.
    Hamel, Angele M.
    Hoang, Chinh T.
    Maffray, Frederic
    DISCRETE APPLIED MATHEMATICS, 2018, 234 : 76 - 85
  • [10] To reorient is easier than to orient: An on-line algorithm for reorientation of graphs
    Fiori-Carones, Marta
    Marcone, Alberto
    COMPUTABILITY-THE JOURNAL OF THE ASSOCIATION CIE, 2021, 10 (03): : 215 - 233
12