Given graphs G and H, a vertex coloring c : V (G) →ℕ is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, χ (H,G), is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G, ∑(H,G), is the minimum value achieved by summing the vertex colors of each H-free coloring of G. We provide a general bound for ∑(H,G), discuss the computational complexity of finding this parameter for different choices of H, and prove an exact formulas for some graphs G. For every integer k and for every graph H, we construct families of graphs, Gk with the property that k more colors than χ (H,G) are required to realize ∑(H,G) for H-free colorings. More complexity results and constructions of graphs requiring extra colors are given for planar and outerplanar graphs.
@article{bwmeta1.element.doi-10_7151_dmgt_1819,
author = {Ewa Kubicka and Grzegorz Kubicki and Kathleen A. McKeon},
title = {Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {35},
year = {2015},
pages = {541-555},
zbl = {1317.05062},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1819}
}
Ewa Kubicka; Grzegorz Kubicki; Kathleen A. McKeon. Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 541-555. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1819/
[1] M. Albertson, R. Jamison, S. Hedetniemi and S. Locke, The subchromatic number of a graph, Discrete Math. 74 (1989) 33-49. doi:10.1016/0012-365X(89)90196-9[Crossref] | Zbl 0681.05033
[2] J. Andrews and M. Jacobson, On a generalization of chromatic number , Congr. Numer. 47 (1985) 33-48.
[3] D. Archdeacon, A note on defective colorings of graphs in surfaces, J. Graph Theory 11 (1987) 517-519. doi:10.1002/jgt.3190110408[Crossref]
[4] M. Borowiecki. I. Broere, M. Frick, P. Mih´ok and G. Semaniˇsin, A survey of hered- itary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50. doi:10.7151/dmgt.1037[Crossref]
[5] I. Broere and M. Mynhardt, Generalized colorings of outer-planar and planar graphs, Graph Theory with Applications to Algorithms and Computer Science, Wiley, New York (1985) 151-161.
[6] I. Broere, S. Dorfing and E. Jonck, Generalized chromatic numbers and hereditary properties of graphs, Discuss. Math. Graph Theory 22 (2002) 259-270. doi:10.7151/dmgt.1174[Crossref] | Zbl 1030.05038
[7] H. Broersma, F.V. Fomin, J. Kratochvil and G.J. Woeginger, Planar graph coloring avoiding monochromatic subgraphs: trees, and paths make it difficult, Algorithmica 44 (2006) 343-361. doi:10.1007/s00453-005-1176-8[Crossref] | Zbl 1095.68075
[8] M.I. Burstein, The bi-colorability of planar hypergraphs, Sakharth. SSR Mecn. Akad. Moambe 78 (1975) 293-296.
[9] G. Chartrand, D. Geller and S. Hedetniemi, A generalization of the chromatic num- ber, Proc. Cambridge Philos. Soc. 64 (1968) 265-271. doi:10.1017/S0305004100042808[Crossref]
[10] G. Chartrand and H. Kronk, The point-arboricity of planar graphs, J. London Math. Soc. 44 (1969) 612-616. doi:10.1112/jlms/s1-44.1.612[Crossref] | Zbl 0175.50505
[11] G. Chartrand, H. Kronk and C. Wall, The point-arboricity of a graph, Israel J. Math. 6 (1968) 169-175. doi:10.1007/BF02760181[Crossref] | Zbl 0164.54201
[12] L.J. Cowen, R.H. Cowen and D.R.Woodall, Defective colorings of graphs in surfaces; partitions into subgraphs of bounded valency, J. Graph Theory 10 (1986) 187-195. doi:10.1002/jgt.3190100207[Crossref] | Zbl 0596.05024
[13] L.J. Cowen, W. Goddard and C.E. Jesurum, Defective colorings revisited, J. Graph Theory 24 (1997) 205-219. doi:10.1002/(SICI)1097-0118(199703)24:3h205::AID-JGT2i3.0.CO;2-T[Crossref] | Zbl 0877.05019
[14] K. Dargen and K. Fraughnaugh, Conditional chromatic numbers with forbidden cycles, Linear Algebra Appl. 217 (1985) 53-66. doi:10.1016/0024-3795(94)00139-5[Crossref] | Zbl 0824.05024
[15] P. Erd˝os, E. Kubicka and A.J. Schwenk, Graphs that require many colors to achieve their chromatic sum, Proc. Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing 71 (1990) 17-28. | Zbl 0704.05020
[16] W. Goddard, Acyclic colorings of planar graphs, Discrete Math. 91 (1991) 91-94. doi:10.1016/0012-365X(91)90166-Y[Crossref]
[17] F. Harary and K. Fraughnaugh (Jones), Conditional colorability II: bipartite varia- tions, Congr. Numer. 50 (1985) 205-218.
[18] F. Harary and K. Fraughnaugh (Jones), Degree conditional bipartition numbers in graphs, Congr. Numer. 55 (1986) 39-50.[WoS]
[19] E. Kubicka, The chromatic sums and efficient tree algorithms, Ph.D. Thesis,Western Michigan University (1989).
[20] E. Kubicka, G. Kubicki and K. McKeon, Chromatic sums for colorings avoiding monochromatic subgraphs, Electron. Notes Discrete Math. 43 (2013) 247-254. doi:10.1016/j.endm.2013.07.041 [Crossref] | Zbl 1317.05062
[21] E. Kubicka and A. Schwenk, Introduction to chromatic sums, Congr. Numer. 71 (1990) 7-28.
[22] K. McKeon, Generalized chromatic numbers of graphs with bipartite complements, Congr. Numer. 197 (2009) 97-105. | Zbl 1211.05045
[23] K. McKeon and H. Pham, Generalized chromatic numbers of graphs with prescribed complements, Congr. Numer. 191 (2008) 71-79. | Zbl 1181.05047
[24] K.S. Poh, On the linear vertex-arboricity of a planar graph, J. Graph Theory 14 (1990) 73-75. doi:10.1002/jgt.3190140108[Crossref] | Zbl 0705.05016
[25] C. Thomassen, Decomposing a planar graph into degenerate graphs, J. Combin. Theory Ser. B 65 (1995) 305-314. doi:10.1006/jctb.1995.1057 [Crossref] | Zbl 0840.05070