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/