Search

A path P in an edge-colored graph G is called a proper path if no two adjacent edges of P are colored the same, and G is proper connected if every two vertices of G are connected by a proper path in G. The proper connection number of a connected graph G, denoted by pc(G), is the minimum number of colors that are needed to make G proper connected. In this paper, we investigate the proper connection number of the complement of a graph G according to some constraints of G itself. Also, we characterize the graphs on n vertices that have proper connection number n-2. Using this result, we give a Nordhaus-Gaddum-type theorem for the proper connection number. We prove that if G and G¯ are both connected, then 4≤pc(G)+pc(G¯)≤n, and the upper bound holds if and only if G or G¯ is the n-vertex tree with maximum degree n-2. [ABSTRACT FROM AUTHOR]

Let colg(G) be the game coloring number of a given graph G. Define the game coloring number of a family of graphs H as colg(H):=max{colg(G):G∈H}. Let Pk be the family of planar graphs of girth at least k. We show that colg(P7)≤5. This result extends a result about the game coloring number by Wang and Zhang [10] (colg(P8)≤5). We also show that these bounds are sharp by constructing a graph G where G∈Pk for each k≤8 such that colg(G)=5. As a consequence, colg(Pk)=5 for k=7,8. [ABSTRACT FROM AUTHOR]

A total coloring of a graph is an assignment of colors to all the elements of the graph in such a way that no two adjacent or incident elements receive the same color. In this paper, we prove Behzad-Vizing conjecture for product graphs. In particular, we obtain the tight bound for certain classes of graphs. [ABSTRACT FROM AUTHOR]

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]

A star coloring of an undirected graph G is a coloring of the vertices of G such that (i) no two adjacent vertices receive the same color, and (ii) no path on four vertices (not necessarily induced) is bi-colored. The star chromatic number of G, denoted by χs(G), is the minimum number of colors needed to star color G. Similar to the notion of χ-boundedness in graphs, we say that a hereditary class of graphs G is χs-bounded if, for some integer valued function f, χs(G)≤f(ω(G)) for every G∈G, where ω(G) is the maximum number of vertices that are pairwise adjacent in G. We show that some classes of perfect graphs, some classes of (P5,C4)-free graphs, and some classes of K1,3-free graphs are χs-bounded. We also give examples in most of the cases to show that the bounds are tight. [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 every $$k \in {\mathbb {N}}_0$$ , we consider graphs in which for any induced subgraph, $$\Delta \le \omega - 1 + k$$ holds, where $$\Delta $$ is the maximum degree and $$\omega $$ is the maximum clique number of the subgraph. We give a finite forbidden induced subgraph characterization for every $$k$$ . As an application, we find some results on the chromatic number $$\chi $$ of a graph. B. Reed stated the conjecture that for every graph, $$\chi \le \lceil \frac{\Delta + \omega + 1 }{2}\rceil $$ holds. Since this inequality is fulfilled by graphs in which $$\Delta \le \omega + 2$$ holds, our results provide a hereditary graph class for which the conjecture holds. [ABSTRACT FROM AUTHOR]

A facial parity edge-coloring of a $$2$$ -edge-connected plane graph is such an edge-coloring in which no two face-adjacent edges receive the same color and in addition, for each face $$f$$ and each color $$c$$ either no edge or an odd number of edges incident with $$f$$ is colored with $$c$$ . Let $$\chi _p^\prime (G)$$ denote the minimum number of colors used in such a coloring of $$G$$ . In this paper we prove that $$\chi _p^\prime (G)\le 9$$ for any $$2$$ -edge-connected outerplane graph $$G$$ with one exception. Moreover, we show that this bound is tight. [ABSTRACT FROM AUTHOR]

This paper deals with extremal problems concerning colorings of partial Steiner systems. We establish a new sufficient condition for r-colorability of a hypergraph from some class of such systems in terms of maximum vertex degree. Moreover, as a corollary we obtain a new lower bound for the threshold probability for r-colorability of a random hypergraph in a binomial model. [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]

Let G be a graph that can be drawn on a plane in such a way that any edge intersects at most one other edge. It is proved that the chromatic number of G does not exceed 7. The bound $ \chi (G)\leq \frac{{9+\sqrt{17+64g }}}{2} $ is also proved for a graph G that can be drawn on a surface of genus g ( g ≥ 1) in such a way that any edge intersects at most one other edge. Bibliography: 8 titles. [ABSTRACT FROM AUTHOR]

A clique-colouring of a graph G is a colouring of the vertices of G so that no maximal clique of size at least two is monochromatic. The clique-hypergraph, $${\mathcal{H}(G)}$$ , of a graph G has V( G) as its set of vertices and the maximal cliques of G as its hyperedges. A vertex-colouring of $${\mathcal{H}(G)}$$ is a clique-colouring of G. Determining the clique-chromatic number, the least number of colours for which a graph G admits a clique-colouring, is known to be NP-hard. In this work, we establish that the clique-chromatic number of powers of cycles is equal to two, except for odd cycles of size at least five, that need three colours. For odd-seq circulant graphs, we show that their clique-chromatic number is at most four, and determine the cases when it is equal to two. Similar bounds for the chromatic number of these graphs are also obtained. [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]

Multi-coloring on the path is a model for frequency assignment in linear cellular networks. Two models have been studied in previous papers: calls may either have finite or infinite duration. For hexagonal networks, a variation of the models where limited frequency reassignment is allowed has also been studied. We add the concept of frequency reassignment to the models of linear cellular networks and close these problems by giving matching upper and lower bounds in all cases. We prove that no randomized algorithm can have a better competitive ratio than the best deterministic algorithms. In addition, we give an exact characterization of the natural greedy algorithms for these problems. All of the above results are with regard to competitive analysis. Taking steps towards a more fine-grained analysis, we consider the case of finite calls and no frequency reassignment and prove that, even though randomization cannot bring the competitive ratio down to one, it seems that the greedy algorithm is expected optimal on uniform random request sequences. We prove this for small paths and indicate it experimentally for larger graphs. [ABSTRACT FROM AUTHOR]

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc( G) of the graph G is the smallest number of colors in a linear coloring of G. In this paper, it is proved that every planar graph G with girth g and maximum degree Δ has (1) lc( G) ≤ Δ + 21 if Δ ≥ 9; (2) $$lc(G) \leqslant \left\lceil {\tfrac{\Delta } {2}} \right\rceil + 7$$ if g ≥ 5; (3) $$lc(G) \leqslant \left\lceil {\tfrac{\Delta } {2}} \right\rceil + 2$$ if g ≥ 7 and Δ≥ 7. [ABSTRACT FROM AUTHOR]