An orientation D of a graph G is a digraph obtained from G by replacing each edge by exactly one of the two possible arcs with the same ends. An orientation D of a graph G is a k-orientation if the in-degree of each vertex in D is at most k. An orientation D of G is proper if any two adjacent vertices have different in-degrees in D. The proper orientation number of a graph G, denoted by →χ (G), is the minimum k such that G has a proper k-orientation. A weighted orientation of a graph G is a pair (D, w), where D is an orientation of G and w is an arc-weighting A(D) → N \ {0}. A semi-proper orientation of G is a weighted orientation (D, w) of G such that for every two adjacent vertices u and v in G, we have that S(d,w)(v) ≠ S(d,w)(u), where S(d,w)(v) is the sum of the weights of the arcs in (D, w) with head v. For a positive integer k, a semi-proper k-orientation (D, w) of a graph G is a semi-proper orientation of G such that maxvϵV(G) S(d,w)(v) ≤ k. The semi-proper orientation number of a graph G, denoted by →χs(G), is the least k such that G has a semi-proper k-orientation. In this work, we first prove that →χs(G) ϵ {ω(G) - 1, ω(G)} for every split graph G, and that, given a split graph G, deciding whether →χs(G) = ω(G) - 1 is an NP-complete problem. We also show that, for every k, there exists a (chordal) graph G and a split subgraph H of G such that →χ(G) ≤ k and →χ(H) = 2k - 2. In the sequel, we show that, for every n ≥ p(p + 1), →χs(Ppn) = [3/2 p], where Ppn is the pth power of the path on n vertices. We investigate further unit interval graphs with no big clique: we show that →χ(G) ≤ 3 for any unit interval graph G with ω(G) = 3, and present a complete characterization of unit interval graphs with →χ(G)= ω(G) = 3. Then, we show that deciding whether →χs(G) = ω(G) can be solved in polynomial time in the class of co-bipartite graphs. Finally, we prove that computing →χs(G) is FPT when parameterized by the minimum size of a vertex cover in G or by the treewidth of G. We also prove that not only computing →χs(G) but also →χ(G), admits a polynomial kernel when parameterized by the neighbourhood diversity plus the value of the solution. These results imply kernels of size 40(k2) and 0(2kk2), in chordal graphs and split graphs, respectively, for the problem of deciding whether →χs(G) ≤ k parameterized by k. We also present exponential kernels for computing both →χ(G) and →χs(G) parameterized by the value of the solution when G is a cograph. On the other hand, we show that computing →χs(G) does not admit a polynomial kernel parameterized by the value of the solution when G is a chordal graph, unless NP ⊆ coNP/poly.

In this paper we study distributed algorithms on massive graphs where links represent a particular relationship between nodes (for instance, nodes may represent phone numbers and links may indicate telephone calls). Since such graphs are massive they need to be processed in a distributed and streaming way. When computing graph theoretic properties, nodes become natural units for distributed computation. Links do not necessarily represent communication channels between the computing units and therefore do not restrict the communication flow. Our goal is to model and analyze the computational power of such distributed systems where one computing unit is assigned to each node. Communication takes place on a whiteboard where each node is allowed to write at most one message. Every node can read the contents of the whiteboard and, when activated, can write one small message based on its local knowledge. When the protocol terminates its output is computed from the final contents of the whiteboard. We describe four synchronization models for accessing the whiteboard. We show that message size and synchronization power constitute two orthogonal hierarchies for these systems. We exhibit problems that {\it separate} these models, i.e., that can be solved in one model but not in a weaker one, even with increased message size. These problems are related to maximal independent set and connectivity. We also exhibit problems that require a given message size independently of the synchronization model.

In this paper we ask which properties of a distributed network can be computed from a few amount of local information provided by its nodes. The distributed model we consider is a restriction of the classical CONGEST (distributed) model and it is close to the simultaneous messages (communication complexity) model defined by Babai, Kimmel and Lokam. More precisely, each of these n nodes-which only knows its own ID and the IDs of its neighbors- is allowed to send a message of O(log n) bits to some central entity, called the referee. Is it possible for the referee to decide some basic structural properties of the network topology G? We show that simple questions like, "does G contain a square?", "does G contain a triangle?" or "Is the diameter of G at most 3?" cannot be solved in general. On the other hand, the referee can decode the messages in order to have full knowledge of G when G belongs to many graph classes such as planar graphs, bounded tree width graphs and, more generally, bounded degeneracy graphs. We leave open questions related to the connectivity of arbitrary graphs.

We investigate the natural situation of the dissemination of information on various graph classes starting with a random set of informed vertices called active. Initially active vertices are chosen independently with probability p, and at any stage in the process, a vertex becomes active if the majority of its neighbours are active, and thereafter never changes its state. This process is a particular case of bootstrap percolation. We show that in any cubic graph, with high probability, the information will not spread to all vertices in the graph if $p<\frac{1}{2}$ . We give families of graphs in which information spreads to all vertices with high probability for relatively small values of p.