Search

The class of 2K2-free graphs and its various subclasses have been studied in a variety of contexts. In this paper, we are concerned with the colouring of (P3∪P2)-free graphs, a super class of 2K2-free graphs. We derive a O(ω3) upper bound for the chromatic number of (P3∪P2)-free graphs, and sharper bounds for (P3∪P2, diamond)-free graphs and for (2K2, diamond)-free graphs, where ω denotes the clique number. The last two classes are perfect if ω≥5 and ≥4 respectively. [ABSTRACT FROM AUTHOR]

A t-tone k-coloring of a graph G=(V,E) is a function f:V→[k]t such that |f(u)∩f(v)| for all distinct vertices u and v. The t-tone chromatic number of G, denoted τt(G), is the smallest positive integer k such that G has a t-tone k-coloring. The Wiener index W(G) of a connected graph G is the sum of the distances of all pairs of vertices of G. In this paper, we prove that τt(G)≥t|V|-W(G)+|V|2 for a connected graph G and obtain a characterization when the equality holds. As a result, for each graph G (not necessarily connected), we obtain a formula for the t-tone chromatic number of G when t is sufficiently large. [ABSTRACT FROM AUTHOR]

We study the distributed low tree-depth decomposition problem for graphs restricted to a bounded expansion class. Low tree-depth decomposition have been introduced in 2006 and have found quite a few applications. For example it yields a linear-time model checking algorithm for graphs in a bounded expansion class. Recall that bounded expansion classes cover classes of graphs of bounded degree, of planar graphs, of graphs of bounded genus, of graphs of bounded treewidth, of graphs that exclude a fixed minor, and many other graphs. There is a sequential algorithm to compute low tree-depth decomposition (with bounded number of colors) in linear time. In this paper, we give the first efficient distributed algorithm for this problem. As it is usual for a symmetry breaking problem, we consider a synchronous model, and as we are interested in a deterministic algorithm, we use the usual assumption that each vertex has a distinct identity number. We consider the distributed message-passing $$\mathcal {CONGEST}_\mathrm{BC}$$ model, in which messages have logarithmic length and only local broadcast are allowed. In this model, we present a logarithmic time distributed algorithm for computing a low tree-depth decomposition of graphs in a fixed bounded expansion class. In the sequential centralized case low tree-depth decomposition linear time algorithm are used as a core procedure in several non-trivial linear time algorithms. We believe that, similarly, low tree-depth decomposition could be at the heart of several non-trivial logarithmic time algorithms. [ABSTRACT FROM AUTHOR]

We call an edge colouring of a graph $$G$$ a rainbow colouring if every pair of vertices is joined by a rainbow path, i.e., a path where no two edges have the same colour. The minimum number of colours required for a rainbow colouring of the edges of $$G$$ is called the rainbow connection number (or rainbow connectivity) $${\mathrm {rc}}(G)$$ of $$G$$ . We investigate sharp thresholds in the Erdős-Rényi random graph for the property ' $${\mathrm {rc}}(G)\le r$$ ' where $$r$$ is a fixed integer. It is known that for $$r=2$$ , rainbow connection number $$2$$ and diameter $$2$$ happen essentially at the same time in random graphs. For $$r \ge 3$$ , we conjecture that this is not the case, propose an alternative threshold, and prove that this is an upper bound for the threshold for rainbow connection number $$r$$ . [ABSTRACT FROM AUTHOR]

For a graph $$X$$ with at most one isolated vertex and without isolated edges, a product-irregular labeling $$\omega :E(X)\rightarrow \{1,2,\ldots ,s\}$$ , first defined by Anholcer in 2009, is a labeling of the edges of $$X$$ such that for any two distinct vertices $$u$$ and $$v$$ of $$X$$ the product of labels of the edges incident with $$u$$ is different from the product of labels of the edges incident with $$v$$ . The minimal $$s$$ for which there exist a product irregular labeling is called the product irregularity strength of $$X$$ and is denoted by $$ps(X)$$ . In this paper it is proved that $$ps(X)\le |V(X)|-1$$ for any graph $$X$$ with more than $$3$$ vertices. Moreover, the connection between the product irregularity strength and the multidimensional multiplication table problem is given, which is especially expressed in the case of the complete multipartite graphs. [ABSTRACT FROM AUTHOR]

An edge-colored graph G is rainbow connected if every pair of vertices of G are connected by a path whose edges have distinct colors. The rainbow connection number rc( G) of G is defined to be the minimum integer t such that there exists an edge-coloring of G with t colors that makes G rainbow connected. For a graph G without any cut vertex, i.e., a 2-connected graph, of order n, it was proved that $${rc(G)\leq\lceil\frac{n}{2} \rceil}$$ and the bound is tight. In this paper, we prove that for a connected graph G of order n with at least one cut vertex, $${rc(G) \leq\frac{n+r-1} 2}$$ , where r is the number of blocks of G with even orders, and the upper bound is tight. Moreover, we also obtain a tight upper bound $${\lfloor(2n-2)/3\rfloor}$$ for the rainbow connection number of a bridgeless (2-edge-connected) graph of order n. [ABSTRACT FROM AUTHOR]

An edge-colored graph G is rainbow connected if every two vertices of G are connected by a path whose edges have distinct colors. The rainbow connection number of G, denoted by rc( G), is the minimum number of colors that are needed to make G rainbow connected. In this paper we give a Nordhaus-Gaddum-type result for the rainbow connection number. We prove that if G and $${\overline{G}}$$ are both connected, then $${4\leq rc(G)+rc(\overline{G})\leq n+2}$$. Examples are given to show that the upper bound is sharp for n ≥ 4, and the lower bound is sharp for n ≥ 8. Sharp lower bounds are also given for n = 4, 5, 6, 7, respectively. [ABSTRACT FROM AUTHOR]