One of the main areas of the project is the investigation of various convexities, related with the metric graph theory. In this article we consider g_3-convexity in a graph G that consists of those sets, whose Steiner interval with respect to any of its three vertices lies in them. Henning et al. (2009) proved that if every j-ball for all j)0 is g_3-convex in a graph G, then G has no induced house nor twin C_4, and every cycle in G of length at least six is well-bridged. In this paper we show that the converse of this theorem is true, thus characterizing the graphs in which all balls are g_3-convex.
COBISS.SI-ID: 16079193
The paper gives a short and elegant proof of an upper bound for the independence number of direct products. Generalizations are also considered, namely the k-independence number of a graph G, as the size of a largest k-colorable subgraph of G. Using this concept a conjecure that is closely related and strengthens the well known Hedetniemi's conjecture is raised, and proved for small values of k.
COBISS.SI-ID: 16079705