Abstract
In this paper we consider a problem of graph \({\mathcal P}\)-coloring consisting in partitioning the vertex set of a graph such that each of the resulting sets induces a graph in a given additive, hereditary class of graphs \({\mathcal P}\). We focus on partitions generated by the greedy algorithm. In particular, we show that given a graph G and an integer k deciding if the greedy algorithm outputs a \({\mathcal P}\)-coloring with a least k colors is \(\mathbb {NP}\)-complete for an infinite number of classes \({\mathcal P}\). On the other hand we get a polynomial-time certifying algorithm if k is fixed and the family of minimal forbidden graphs defining the class \({\mathcal P}\) is finite. We also prove \(\mathrm{co}\mathbb {NP}\)-completeness of the problem of deciding whether for a given graph G the difference between the largest number of colors used by the greedy algorithm and the minimum number of colors required in any \({\mathcal P}\)-coloring of G is bounded by a given constant. A new Brooks-type bound on the largest number of colors used by the greedy \({\mathcal P}\)-coloring algorithm is given.
Supported by the Polish National Science Center grant DEC-2011/02/A/ST6/00201.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Araujo, J., Linhares-Sales, C.: On the Grundy number of graphs with few \(P_4\)’s. Discret. Appl. Math. 160(18), 2514–2522 (2012). doi:10.1016/j.dam.2011.08.016
Borowiecki, P., Rautenbach, D.: New potential functions for greedy independence and coloring. Discret. Appl. Math. 182, 61–72 (2015). doi:10.1016/j.dam.2013.12.011
Borowiecki, P., Sidorowicz, E.: Dynamic coloring of graphs. Fund. Inform. 114(2), 105–128 (2012). doi:10.3233/FI-2012-620
Brown, J.I.: The complexity of generalized graph colorings. Discret. Appl. Math. 69(3), 257–270 (1996). doi:10.1016/0166-218X(96)00096-0
Choudum, S.A., Karthick, T.: First-Fit coloring of \(\{P_5, K_4-e\}\)-free graphs. Discret. Appl. Math. 158(6), 620–626 (2010). doi:10.1016/j.dam.2009.12.009
Christen, C.A., Selkow, S.M.: Some perfect coloring properties of graphs. J. Comb. Theory Ser. B 27(1), 49–59 (1979). doi:10.1016/0095-8956(79)90067-4
Cockayne, E.J., Miller, G.G., Prins, G.: An interpolation theorem for partitions which are complete with respect to hereditary properties. J. Comb. Theory Ser. B 13, 290–297 (1972)
Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1(3), 237–267 (1976)
Golovach, P.A., Johnson, M., Paulusma, D., Song, J.: A survey on the complexity of coloring graphs with forbidden subgraphs. J. Graph Theory 84, 331–363 (2017)
Goyal, N., Vishwanathan, S.: NP-completeness of undirected Grundy numberings and related problems (1998, unpublished manuscript)
Gyárfás, A., Király, Z., Lehel, J.: On-line 3-chromatic graphs II. Critical graphs. Discret. Math. 177(1–3), 99–122 (1997). doi:10.1016/S0012-365X(96)00359-7
Gyárfás, A., Lehel, J.: First-Fit and on-line chromatic number of families of graphs. Ars Comb. 29C, 168–176 (1990)
Hedetniemi, S.M., Hedetniemi, S.T., Beyer, T.: A linear algorithm for the Grundy (coloring) number of a tree. Congr. Numer. 36, 351–363 (1982)
Kierstead, H.A.: Coloring graphs on-line. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms. LNCS, vol. 1442, pp. 281–305. Springer, Heidelberg (1998). doi:10.1007/BFb0029574
Kortsarz, G.: A lower bound for approximating Grundy numbering. Discret. Math. Theor. Comput. Sci. 9, 7–22 (2007)
Narayanaswamy, N.S., Babu, R.S.: A note on first-fit coloring of interval graphs. Order 25(1), 49–53 (2008). doi:10.1007/s11083-008-9076-6
Zaker, M.: Results on the Grundy chromatic number of graphs. Discret. Math. 306(23), 3166–3173 (2006). doi:10.1016/j.disc.2005.06.044
Zaker, M.: New bounds for the chromatic number of graphs. J. Graph Theory 58(2), 110–122 (2008). doi:10.1002/jgt.20298
Acknowledgements
Special thanks to D. Dereniowski, E. Drgas-Burchardt and anonymous referees for their remarks on preliminary version of this paper, and to S. Vishwanathan for sending the manuscript [10].
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Borowiecki, P. (2017). On Computational Aspects of Greedy Partitioning of Graphs. In: Xiao, M., Rosamond, F. (eds) Frontiers in Algorithmics. FAW 2017. Lecture Notes in Computer Science(), vol 10336. Springer, Cham. https://doi.org/10.1007/978-3-319-59605-1_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-59605-1_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-59604-4
Online ISBN: 978-3-319-59605-1
eBook Packages: Computer ScienceComputer Science (R0)