In a graph, by definition, the weight of a (proper) coloring with positive integers is the sum of the colors. The chromatic sum is the minimum weight, taken over all the proper colorings. The minimum number of colors in a coloring of minimum weight is the cost chromatic number or strength of the graph. We derive general upper bounds for the strength, in terms of a new parameter of representations by edge intersections of hypergraphs.
Let G = (V,E) be a graph, and k ≥ 1 an integer. A subgraph D is said to be k-dominating in G if every vertex of G-D is at distance at most k from some vertex of D. For a given class 𝓓 of graphs, Domₖ 𝓓 is the set of those graphs G in which every connected induced subgraph H has some k-dominating induced subgraph D ∈ 𝓓 which is also connected. In our notation, Dom𝓓 coincides with Dom₁𝓓. In this paper we prove that $Dom Dom 𝓓_u = Dom₂ 𝓓_u$ holds for $𝓓_u$ = {all connected graphs without induced $P_u$} (u ≥ 2). (In particular, 𝓓₂ = {K₁} and 𝓓₃ = {all complete graphs}.) Some negative examples are also given.
A graph G is hereditarily dominated by a class 𝓓 of connected graphs if each connected induced subgraph of G contains a dominating induced subgraph belonging to 𝓓. In this paper we characterize graphs hereditarily dominated by classes of complete bipartite graphs, stars, connected bipartite graphs, and complete k-partite graphs.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.