Let G → = (V,A) be an oriented graph, G = (V,E) the underlying graph of G → and k be a positive integer. An oriented k-coloring of G → is a partition of V into k subsets, such that there are no two adjacent vertices belonging to the same subset, and all the arcs between a pair of subsets have the same orientation. The oriented chromatic number χ ° (G → ) of G → is the smallest k , such that G → admits an oriented k -coloring. The oriented chromatic number of G, denoted by χ ° (G), is the maximum of χ ° (G → ) for all orientations G → of G . Given two graphs G and H with V(G) n V(H) = θ, we say that G U H is the disjoint union graph of G and H , if V(G U H) = V(G) U V(H) and E(G U H) = E(G) U E(H). A wheel graph W q ,q ≥ 3 has V(W q ) = {v1, v2, ... ,v q ,c} and E(Wq) = {v i -v i+1 : i ε {1,2,...,q- 1}} U { v q v 1 } U { v i c : i ε {1,2,...,q}}. Wheel graphs consist of a important class having many theoretical and algorithmic applications with an ample literature on coloring problems. Bounds for the oriented coloring of wheel graphs were evaluated on the literature, but the exact values were not known. In this paper we determine the exact value of χ o (W q ) as q + 1 when 3 ≤ q ≤ 6, 7 whether q =7 and 8 whether q ≥ 8, producing a linear time algorithm to color any wheel graph. Let K p be the complete graph with p ≥ 1 vertices, when q ≤ 8 we give exact values for χ o (K p U W q ) and for large values of q ≥ 9 we show that χ o (K p U W q ) is either p + 2 or p + 3.

The influence of individuals in a network and its propagation is dealt with in several studies in the literature. A well-known model is the majority target set, in which if most of the neighbors of an individual in the network are influenced, then the individual is also influenced. Finding a majority target set of minimum size is an NP-hard problem for general graphs. This paper proposes a heuristic for this problem, which has faster runtimes and achieves better solution values than related works, both on small random instances and on large real social network graphs.

Let ⃗G = (V, A) be an oriented graph. An oriented k-coloring of ⃗G is a partition of V into k color classes, such that there is no pair of adjacent vertices belonging to the same class and all the arcs between a pair of color classes have the same orientation. The smallest k such that ⃗G admits an oriented k-coloring is the oriented chromatic number Xo(⃗G) = k of ⃗G. In an oriented coloring of ⃗G every pair of vertices with oriented distance at most 2 in ⃗G have different colors. In 2004, Klostermeyer and MacGillivray defined the concept of an “analogue of clique” for oriented coloring in which a subgraph ⃗H of ⃗G is an oriented clique if every pair of vertices of ⃗H is in an oriented distance of at most 2 in ⃗H. The authors defined the absolute oriented clique number of ⃗G as the number of vertices |V(H)| = ωao(⃗G) of the largest oriented clique ⃗H of ⃗G and satisfies that ωao(⃗G) ≤ Xo(⃗G). Ever since, for almost 20 years, the time complexity status of this parameter remained unknown. The relative oriented clique number ωao(⃗G) of an oriented graph ⃗G is the size of the largest set of vertices R, such that every pair of vertices of R is at a maximum oriented distance of 2 in R. For every oriented graph ⃗G, ωao(⃗G) ≤ ωro(⃗G) ≤ Xo(⃗G). In this paper we classify Absolute Oriented Clique - the Klostermeyer and Mac Gillivray's decision problem - proving that given an oriented graph ⃗G and a positive integer k it is NP-complete to decide whether ωao(⃗G) ≥ k. We prove that for all ε > 0, there is no polynomial-time approximation for Relative Oriented Clique and for Absolute Oriented Clique within a factor of n1_ε, unless P = NP. Finally, we prove that Relative Oriented Clique is W[1]-complete and that Absolute Oriented Clique belongs to W[2] and is W[1]-hard.

The spread of influence in a social network, diseases in a community, or failures on an interconnected site are topics studied in various fields. Convexity in graphs is a powerful framework for modeling this diffusion behavior. The Carathéodory number is an interesting convexity parameter that can be analyzed to understand the dynamics of this behavior. It is known to be NP-Complete. In this paper, we establish some bounds on the P3-Carathéodory number of graphs with diameter two. For a biconnected diameter-two graph G it holds that c(G) ≤ ∆ +1, while diameter-two with cut-vertex has c(G) = 2. In addition, we show that the P3-Caratheodory number of biconnected C6-free diameter-two graphs is at most 4.

Let $G$ be a finite, simple, and undirected graph and let $S$ be a set of vertices of $G$. If no vertex of $G$ that does not belong to $S$ has two neighbors in $S$, then $S$ is $P_3$-convex. The $P_3$-convex hull $H_G(S)$ of $S$ is the smallest $P_3$-convex set containing $S$. The $P_3$-Carathéodory number of $G$ is the smallest integer $c$ such that for every set $S$ and every vertex $u$ in $H_G(S)$, there is a set $F\subseteq S$ with $|F|\leq c$ and $u\in H_G(F)$. We study structural and algorithmic aspects of the $P_3$-Carathéodory number. We characterize the $P_3$-Carathéodory number of trees and block graphs, establish upper bounds on the $P_3$-Carathéodory number of general graphs and of claw-free graphs, and prove that it is NP-complete to decide for a given bipartite graph $G$ and a given integer $k$ whether the $P_3$-Carathéodory number of $G$ is at least $k$.