Search

Abstract: We study a robustness model for the minimum coloring problem, where any vertex of the input-graph has some presence probability . We show that, under this model, the original coloring problem gives rise to a new coloring version (called Probabilistic Min Coloring) where the objective becomes to determine a partition of into independent sets , that minimizes the quantity , where, for any independent set , . We show that Probabilistic Min Coloring is NP-hard and design a polynomial time approximation algorithm achieving non-trivial approximation ratio. We then focus ourselves on probabilistic coloring of bipartite graphs and show that the problem of determining the best k-coloring (called Probabilistic Min -Coloring) is NP-hard, for any . We finally study Probabilistic Min Coloring and Probabilistic Min -Coloring in a particular family of bipartite graphs that plays a crucial role in the proof of the NP-hardness result just mentioned, and in complements of bipartite graphs. [Copyright &y& Elsevier]

It is known that the independence number of a connected claw-free graph G of order n is at most (n+1)/2. We improve this result by showing that this bound still holds for the upper irredundance number IR(G). We characterize the connected claw-free graphs for which IR(G)=(n+1)/2 and give some properties of those graphs for which IR(G)=n/2 if n is even or IR(G)=(n−1)/2 if n is odd. [Copyright &y& Elsevier]