Bipartite rainbow numbers of matchings

Given two graphs G and H, let f(G,H) denote the maximum number c for which there is a way to color the edges of G with c colors such that every subgraph H of G has at least two edges of the same color. Equivalently, any edge-coloring of G with at least rb(G,H)=f(G,H)+1 colors contains a rainbow copy of H, where a rainbow subgraph of an edge-colored graph is such that no two edges of it have the same color. The number rb(G,H) is called the rainbow number ofHwith respect toG, and simply called the bipartite rainbow number ofH if G is the complete bipartite graph K_m,n. Erd?s, Simonovits and Sós showed that rb(K_n,K₃)=n. In 2004, Schiermeyer determined the rainbow numbers rb(K_n,K_k) for all n≥k≥4, and the rainbow numbers rb(K_n,kK₂) for all k≥2 and n≥3k+3. In this paper we will determine the rainbow numbers rb(K_m,n,kK₂) for all k≥1.     

The rainbow connection of a graph is (at most) reciprocal to its minimum degree

An edge‐colored graph Gis rainbow edge‐connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make Grainbow edge‐connected. We prove that if Ghas nvertices and minimum degree δ then rc(G)<20n/δ. This solves open problems from Y. Caro, A. Lev, Y. Roditty, Z. Tuza, and R. Yuster (Electron J Combin 15 (2008), #R57) and S. Chakrborty, E. Fischer, A. Matsliah, and R. Yuster (Hardness and algorithms for rainbow connectivity, Freiburg (2009), pp. 243–254). A vertex‐colored graph Gis rainbow vertex‐connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex‐connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make Grainbow vertex‐connected. One cannot upper‐bound one of these parameters in terms of the other. Nevertheless, we prove that if Ghas nvertices and minimum degree δ then rvc(G)<11n/δ. We note that the proof in this case is different from the proof for the edge‐colored case, and we cannot deduce one from the other. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 185–191, 2010     

Rainbow Connection Number of Graph Power and Graph Products

Rainbow connection number, rc(G), of a connected graph G is the minimum number of colors needed to color its edges so that every pair of vertices is connected by at least one path in which no two edges are colored the same (note that the coloring need not be proper). In this paper we study the rainbow connection number with respect to three important graph product operations (namely the Cartesian product, the lexicographic product and the strong product) and the operation of taking the power of a graph. In this direction, we show that if G is a graph obtained by applying any of the operations mentioned above on non-trivial graphs, then rc(G) ≤ 2r(G) + c, where r(G) denotes the radius of G and \({c \in \{0, 1, 2\}}\) . In general the rainbow connection number of a bridgeless graph can be as high as the square of its radius [1]. This is an attempt to identify some graph classes which have rainbow connection number very close to the obvious lower bound of diameter (and thus the radius). The bounds reported are tight up to additive constants. The proofs are constructive and hence yield polynomial time \({(2 + \frac{2}{r(G)})}\) -factor approximation algorithms.     

Some Remarks on Rainbow Connectivity

An edge (vertex) colored graph is rainbow‐connected if there is a rainbow path between any two vertices, i.e. a path all of whose edges (internal vertices) carry distinct colors. Rainbow edge (vertex) connectivity of a graph G is the smallest number of colors needed for a rainbow edge (vertex) coloring of G. In this article, we propose a very simple approach to studying rainbow connectivity in graphs. Using this idea, we give a unified proof of several known results, as well as some new ones.     

Note on Minimally d-Rainbow Connected Graphs

An edge-colored graph G, where adjacent edges may have the same color, is rainbow connected if every two vertices of G are connected by a path whose edges have distinct colors. A graph G is d-rainbow connected if one can use d colors to make G rainbow connected. For integers n and d let t(n, d) denote the minimum size (number of edges) in d-rainbow connected graphs of order n. Schiermeyer got some exact values and upper bounds for t(n, d). However, he did not present a lower bound of t(n, d) for \({3 \leq d < \lceil\frac{n}{2}\rceil}\) . In this paper, we improve his lower bound of t(n, 2), and get a lower bound of t(n, d) for \({3 \leq d < \lceil\frac{n}{2}\rceil}\) .     

Upper Bounds for the Rainbow Connection Numbers of Line Graphs

A path in an edge-colored graph G, where adjacent edges may be colored the same, is called a rainbow path if no two edges of it are colored the same. A nontrivial connected graph G is rainbow connected if for any two vertices of G there is a rainbow path connecting them. The rainbow connection number of G, denoted rc(G), is defined as the smallest number of colors such that G is rainbow connected. In this paper, we mainly study the rainbow connection number rc(L(G)) of the line graph L(G) of a graph G which contains triangles. We get two sharp upper bounds for rc(L(G)), in terms of the number of edge-disjoint triangles of G. We also give results on the iterated line graphs.     

Rainbows in the Hypercube

Let Q_n be a hypercube of dimension n, that is, a graph whose vertices are binary n-tuples and two vertices are adjacent iff the corresponding n-tuples differ in exactly one position. An edge coloring of a graph H is called rainbow if no two edges of H have the same color. Let f(G,H) be the largest number of colors such that there exists an edge coloring of G with f(G,H) colors such that no subgraph isomorphic to H is rainbow. In this paper we start the investigation of this anti-Ramsey problem by providing bounds on f(Q_n,Q_k) which are asymptotically tight for k = 2 and by giving some exact results.     

Rainbow and monochromatic circuits and cocircuits in binary matroids

Given a matroid together with a coloring of its ground set, a subset of its elements is called rainbow colored if no two of its elements have the same color. We show that if an n-element rank r binary matroid M is colored with exactly r colors, then M either contains a rainbow colored circuit or a monochromatic cocircuit. As the class of binary matroids is closed under taking duals, this immediately implies that if M is colored with exactly $n?r$ colors, then M either contains a rainbow colored cocircuit or a monochromatic circuit. As a byproduct, we give a characterization of binary matroids in terms of reductions to partition matroids.Motivated by a conjecture of Bérczi, Schwarcz and Yamaguchi, we also analyze the relation between the covering number of a binary matroid and the maximum number of colors or the maximum size of a color class in any of its rainbow circuit-free colorings. For simple graphic matroids, we show that there exists a rainbow circuit-free coloring that uses each color at most twice only if the graph is $(2,3)$-sparse, that is, it is independent in the 2-dimensional rigidity matroid. Furthermore, we give a complete characterization of minimally rigid graphs admitting such a coloring.     

A Necessary and Sufficient Condition for the Existence of a Heterochromatic Spanning Tree in a Graph

We prove the following theorem. An edge-colored (not necessary to be proper) connected graph G of order n has a heterochromatic spanning tree if and only if for any r colors (1≤r≤n−2), the removal of all the edges colored with these r colors from G results in a graph having at most r+1 components, where a heterochromatic spanning tree is a spanning tree whose edges have distinct colors.     

The Sigma Chromatic Number of a Graph

For a nontrivial connected graph G, let ${c: V(G)\to {{\mathbb N}}}For a nontrivial connected graph G, let c: V(G)? \mathbb N{c: V(G)\to {{\mathbb N}}} be a vertex coloring of G, where adjacent vertices may be colored the same. For a vertex v of G, let N(v) denote the set of vertices adjacent to v. The color sum σ(v) of v is the sum of the colors of the vertices in N(v). If σ(u) ≠ σ(v) for every two adjacent vertices u and v of G, then c is called a sigma coloring of G. The minimum number of colors required in a sigma coloring of a graph G is called its sigma chromatic number σ(G). The sigma chromatic number of a graph G never exceeds its chromatic number χ(G) and for every pair a, b of positive integers with a ≤ b, there exists a connected graph G with σ(G) = a and χ(G) = b. There is a connected graph G of order n with σ(G) = k for every pair k, n of positive integers with k ≤n if and only if k ≠ n − 1. Several other results concerning sigma chromatic numbers are presented.     

Rainbow Connection and Graph Products

A path in an edge colored graph G is called a rainbow path if all its edges have pairwise different colors. Then G is rainbow connected if there exists a rainbow path between every pair of vertices of G and the least number of colors needed to obtain a rainbow connected graph is the rainbow connection number. If we demand that there must exist a shortest rainbow path between every pair of vertices, we speak about strongly rainbow connected graph and the strong rainbow connection number. In this paper we study the (strong) rainbow connection number on the direct, strong, and lexicographic product and present several upper bounds for these products that are attained by many graphs. Several exact results are also obtained.     

Rainbow Connection in 3-Connected Graphs

An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In this paper, we proved that rc(G) ≤ 3(n + 1)/5 for all 3-connected graphs.     

Nordhaus–Gaddum-Type Theorem for Rainbow Connection Number of Graphs

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.     

On the b-continuity property of graphs

This paper deals with b-colorings of a graph G, that is, proper colorings in which for each color c, there exists at least one vertex colored by c such that its neighbors are colored by each other color. The b-chromatic numberb(G) of a graph G is the maximum number of colors for which G has a b-coloring. It is easy to see that every graph G has a b-coloring using χ(G) colors.We say that G is b-continuous iff for each k, χ(G)?k?b(G), there exists a b-coloring with k colors. It is well known that not all graphs are b-continuous. We call b-spectrumS_b(G) of G to be the set of integers k for which there is a b-coloring of G by k colors. We show that for any finite integer set I, there exists a graph whose b-spectrum is I and we investigate the complexity of the problem of deciding whether a graph G is b-continuous, even if b-colorings using χ(G) and b(G) colors are given.     

Game chromatic index of k‐degenerate graphs

We consider the following edge coloring game on a graph G. Given t distinct colors, two players Alice and Bob, with Alice moving first, alternately select an uncolored edge e of G and assign it a color different from the colors of edges adjacent to e. Bob wins if, at any stage of the game, there is an uncolored edge adjacent to colored edges in all t colors; otherwise Alice wins. Note that when Alice wins, all edges of G are properly colored. The game chromatic index of a graph G is the minimum number of colors for which Alice has a winning strategy. In this paper, we study the edge coloring game on k‐degenerate graphs. We prove that the game chromatic index of a k‐degenerate graph is at most Δ + 3k − 1, where Δ is the maximum vertex degree of the graph. We also show that the game chromatic index of a forest of maximum degree 3 is at most 4 when the forest contains an odd number of edges. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 144–155, 2001     

Neighbor Sum Distinguishing Index

We consider proper edge colorings of a graph G using colors of the set {1, . . . , k}. Such a coloring is called neighbor sum distinguishing if for any pair of adjacent vertices x and y the sum of colors taken on the edges incident to x is different from the sum of colors taken on the edges incident to y. The smallest value of k in such a coloring of G is denoted by ndi_Σ(G). In the paper we conjecture that for any connected graph G ≠ C ₅ of order n ≥ 3 we have ndi_Σ(G) ≤ Δ(G) + 2. We prove this conjecture for several classes of graphs. We also show that ndi_Σ(G) ≤ 7Δ(G)/2 for any graph G with Δ(G) ≥ 2 and ndi_Σ(G) ≤ 8 if G is cubic.     

Dynamic list coloring of bipartite graphs

A dynamic coloring of a graph is a proper coloring of its vertices such that every vertex of degree more than one has at least two neighbors with distinct colors. The least number of colors in a dynamic coloring of G, denoted by χ₂(G), is called the dynamic chromatic number of G. The least integer k, such that if every vertex of G is assigned a list of k colors, then G has a proper (resp. dynamic) coloring in which every vertex receives a color from its own list, is called the choice number of G, denoted by ch(G) (resp. the dynamic choice number, denoted by ch₂(G)). It was recently conjectured (Akbari et al. (2009) [1]) that for any graph G, ch₂(G)=max(ch(G),χ₂(G)). In this short note we disprove this conjecture. We first give an example of a small planar bipartite graph G with ch(G)=χ₂(G)=3 and ch₂(G)=4. Then, for any integer k≥5, we construct a bipartite graph G_k such that ch(G_k)=χ₂(G_k)=3 and ch₂(G)≥k.     

The game of arboricity

Using a fixed set of colors C, Ann and Ben color the edges of a graph G so that no monochromatic cycle may appear. Ann wins if all edges of G have been colored, while Ben wins if completing a coloring is not possible. The minimum size of C for which Ann has a winning strategy is called the game arboricity of G, denoted by A_g(G). We prove that A_g(G)?3k for any graph G of arboricity k, and that there are graphs such that A_g(G)?2k-2. The upper bound is achieved by a suitable version of the activation strategy, used earlier for the vertex coloring game. We also provide two other strategies based on induction and acyclic colorings.     

Partitioning infinite trees

A graph G is bisectable if its edges can be colored by two colors so that the resulting monochromatic subgraphs are isomorphic. We show that any infinite tree of maximum degree Δ with infinitely many vertices of degree at least Δ −1 is bisectable as is any infinite tree of maximum degree Δ ≤ 4. Further, it is proved that every infinite tree T of finite maximum degree contains a finite subset E of its edges so that the graph T − E is bisectable. To measure how “far” a graph G is from being bisectable, we define c(G) to be the smallest number k > 1 so that there is a coloring of the edges of G by k colors with the property that any two monochromatic subgraphs are isomorphic. An upper bound on c(G), which is in a sense best possible, is presented. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 113–127, 2000     

Complete solution for the rainbow numbers of matchings

For a given graph H and a positive n, the rainbow number ofH, denoted by rb(n,H), is the minimum integer k so that in any edge-coloring of K_n with k colors there is a copy of H whose edges have distinct colors. In 2004, Schiermeyer determined rb(n,kK₂) for all n≥3k+3. The case for smaller values of n (namely, ) remained generally open. In this paper we extend Schiermeyer’s result to all plausible n and hence determine the rainbow number of matchings.