Geodesic
Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 3, pp. 541-555.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: coloring, sum of colors, forbidden subgraphs 
@article{DMGT_2015_35_3_a11,
     author = {Kubicka, Ewa and Kubicki, Grzegorz and McKeon, Kathleen A.},
     title = {Chromatic {Sums} for {Colorings} {Avoiding} {Monochromatic} {Subgraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {541--555},
     publisher = {mathdoc},
     volume = {35},
     number = {3},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a11/}
}
TY  - JOUR
AU  - Kubicka, Ewa
AU  - Kubicki, Grzegorz
AU  - McKeon, Kathleen A.
TI  - Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 541
EP  - 555
VL  - 35
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a11/
LA  - en
ID  - DMGT_2015_35_3_a11
ER  - 
%0 Journal Article
%A Kubicka, Ewa
%A Kubicki, Grzegorz
%A McKeon, Kathleen A.
%T Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 541-555
%V 35
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a11/
%G en
%F DMGT_2015_35_3_a11
Kubicka, Ewa; Kubicki, Grzegorz; McKeon, Kathleen A. Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 3, pp. 541-555. http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a11/

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[15] P. Erdős, 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.

[16] W. Goddard, Acyclic colorings of planar graphs, Discrete Math. 91 (1991) 91-94. doi:10.1016/0012-365X(91)90166-Y

[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.

[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

[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.

[23] K. McKeon and H. Pham, Generalized chromatic numbers of graphs with prescribed complements, Congr. Numer. 191 (2008) 71-79.

[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

[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