Dynamic F-free Coloring of Graphs

被引:0
作者
Piotr Borowiecki
Elżbieta Sidorowicz
机构
[1] Gdańsk University of Technology,Department of Algorithms and System Modeling, Faculty of Electronics, Telecommunications and Informatics
[2] University of Zielona Góra,Department of Discrete Mathematics and Theoretical Computer Science, Faculty of Mathematics, Computer Science and Econometrics
来源
Graphs and Combinatorics | 2018年 / 34卷
关键词
Graph coloring; Subcoloring; Improper coloring; Greedy algorithm; Grundy number; 68R10; 05C85; 05C15; 05C75;
D O I
暂无
中图分类号
学科分类号
摘要
A problem of graph F-free coloring consists in partitioning the vertex set of a graph such that none of the resulting sets induces a graph containing a fixed graph F as an induced subgraph. In this paper we consider dynamic F-free coloring in which, similarly as in online coloring, the graph to be colored is not known in advance; it is gradually revealed to the coloring algorithm that has to color each vertex upon request as well as handle any vertex recoloring requests. Our main concern is the greedy approach and characterization of graph classes for which it is possible to decide in polynomial time whether for the fixed forbidden graph F and positive integer k the greedy algorithm ever uses more than k colors in dynamic F-free coloring. For various classes of graphs we give such characterizations in terms of a finite number of minimal forbidden graphs thus solving the above-mentioned problem for the so-called F-trees when F is 2-connected, and for classical trees, when F is a path of order 3 (the latter variant is also known as subcoloring or 1-improper coloring).
引用
收藏
页码:457 / 475
页数:18
相关论文
共 50 条
[41]   On the P3 Coloring of Graphs [J].
Yang, Hong ;
Naeem, Muhammad ;
Qaisar, Shahid .
SYMMETRY-BASEL, 2023, 15 (02)
[42]   Cut-Colorings in Coloring Graphs [J].
Bhakta, Prateek ;
Buckner, Benjamin Brett ;
Farquhar, Lauren ;
Kamat, Vikram ;
Krehbiel, Sara ;
Russell, Heather M. .
GRAPHS AND COMBINATORICS, 2019, 35 (01) :239-248
[43]   Coloring chip configurations on graphs and digraphs [J].
Borowiecki, Mieczyslaw ;
Grytczuk, Jaroslaw ;
Pilsniak, Monika .
INFORMATION PROCESSING LETTERS, 2012, 112 (1-2) :1-4
[44]   On equitable near proper coloring of graphs [J].
Jose, Sabitha ;
Samuel, Libin Chacko ;
Naduvath, Sudev .
COMMUNICATIONS IN COMBINATORICS AND OPTIMIZATION, 2024, 9 (01) :131-143
[45]   Partitioning and coloring graphs with degree constraints [J].
Rabern, Landon .
DISCRETE MATHEMATICS, 2013, 313 (09) :1028-1034
[46]   On 3-Coloring Circle Graphs [J].
Bachmann, Patricia ;
Rutter, Ignaz ;
Stumpf, Peter .
GRAPH DRAWING AND NETWORK VISUALIZATION, GD 2023, PT I, 2023, 14465 :152-160
[47]   b-coloring of tight graphs [J].
Havet, Frederic ;
Sales, Claudia Linhares ;
Sampaio, Leonardo .
DISCRETE APPLIED MATHEMATICS, 2012, 160 (18) :2709-2715
[48]   Coloring graphs with forbidden induced subgraphs [J].
Chudnovsky, Maria .
PROCEEDINGS OF THE INTERNATIONAL CONGRESS OF MATHEMATICIANS (ICM 2014), VOL IV, 2014, :291-302
[49]   (k, 1)-coloring of sparse graphs [J].
Borodin, O. V. ;
Ivanova, A. O. ;
Montassier, M. ;
Raspaud, A. .
DISCRETE MATHEMATICS, 2012, 312 (06) :1128-1135
[50]   On the b-dominating coloring of graphs [J].
Hoàng, CT ;
Kouider, M .
DISCRETE APPLIED MATHEMATICS, 2005, 152 (1-3) :176-186