Name
Abstract | ||
|---|---|---|
Given graphs G and H, a vertex coloring c : V(G) -> N is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, chi(H, G), is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G, Sigma(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 Sigma(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, G(k) with the property that k more colors than chi (H, G) are required to realize Sigma(H, G) for H-free colorings. More complexity results and constructions of graphs requiring extra colors are given for planar and outerplanar graphs. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.7151/dmgt.1819 | DISCUSSIONES MATHEMATICAE GRAPH THEORY |
Keywords | Field | DocType |
coloring,sum of colors,forbidden subgraphs | Discrete mathematics,Monochromatic color,Combinatorics,Chromatic scale,Greedy coloring,Mathematics | Journal |
Volume | Issue | ISSN |
35 | 3 | 1234-3099 |
Citations | PageRank | References |
1 | 0.45 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ewa Kubicka | 1 | 66 | 9.61 |
| Grzegorz Kubicki | 2 | 95 | 15.16 |
| Kathleen A. McKeon | 3 | 36 | 6.94 |