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.     

Upper bounds on vertex distinguishing chromatic index of some Halin graphs

A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph G is denoted by ???? _s (G). In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with ??(G) ?? 4, respectively.     

Coloring, location and domination of corona graphs

A vertex coloring of a graph G is an assignment of colors to the vertices of G so that every two adjacent vertices of G have different colors. A coloring related property of a graphs is also an assignment of colors or labels to the vertices of a graph, in which the process of labeling is done according to an extra condition. A set S of vertices of a graph G is a dominating set in G if every vertex outside of S is adjacent to at least one vertex belonging to S. A domination parameter of G is related to those structures of a graph that satisfy some domination property together with other conditions on the vertices of G. In this article we study several mathematical properties related to coloring, domination and location of corona graphs. We investigate the distance-k colorings of corona graphs. Particularly, we obtain tight bounds for the distance-2 chromatic number and distance-3 chromatic number of corona graphs, through some relationships between the distance-k chromatic number of corona graphs and the distance-k chromatic number of its factors. Moreover, we give the exact value of the distance-k chromatic number of the corona of a path and an arbitrary graph. On the other hand, we obtain bounds for the Roman dominating number and the locating–domination number of corona graphs. We give closed formulaes for the k-domination number, the distance-k domination number, the independence domination number, the domatic number and the idomatic number of corona graphs.     

Graphs with 1-Hamiltonian-connected cubes

The cube G³ of a connected graph G is that graph having the same vertex set as G and in which two distinct vertices are adjacent if and only if their distance in G is at most three. A Hamiltonian-connected graph has the property that every two distinct vertices are joined by a Hamiltonian path. A graph G is 1-Hamiltonian-connected if, for every vertex w of G, the graphs G and G?w are Hamiltonian-connected. A characterization of graphs whose cubes are 1-Hamiltonian-connected is presented.     

The harmonious coloring problem is NP-complete for interval and permutation graphs

In this paper, we prove that the harmonious coloring problem is NP-complete for connected interval and permutation graphs. Given a simple graph G, a harmonious coloring of G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number is the least integer k for which G admits a harmonious coloring with k colors. Extending previous work on the NP-completeness of the harmonious coloring problem when restricted to the class of disconnected graphs which are simultaneously cographs and interval graphs, we prove that the problem is also NP-complete for connected interval and permutation graphs.     

Improved bounds on linear coloring of plane graphs

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, we give some upper bounds on linear chromatic number for plane graphs with respect to their girth, that improve some results of Raspaud and Wang (2009).     

Crossing graphs of fiber-complemented graphs

Fiber-complemented graphs form a vast non bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph G as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in G. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal.     

Crossing graphs of fiber-complemented graphs

Fiber-complemented graphs form a vast non-bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph G as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in G. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal.     

Partitioning 2-edge-colored graphs by monochromatic paths and cycles

We present results on partitioning the vertices of 2-edge-colored graphs into monochromatic paths and cycles. We prove asymptotically the two-color case of a conjecture of Sárközy: the vertex set of every 2-edge-colored graph can be partitioned into at most 2α(G) monochromatic cycles, where α(G) denotes the independence number of G. Another direction, emerged recently from a conjecture of Schelp, is to consider colorings of graphs with given minimum degree. We prove that apart from o(|V (G)|) vertices, the vertex set of any 2-edge-colored graph G with minimum degree at least \(\tfrac{{(1 + \varepsilon )3|V(G)|}} {4}\) can be covered by the vertices of two vertex disjoint monochromatic cycles of distinct colors. Finally, under the assumption that \(\bar G\) does not contain a fixed bipartite graph H, we show that in every 2-edge-coloring of G, |V (G)| ? c(H) vertices can be covered by two vertex disjoint paths of different colors, where c(H) is a constant depending only on H. In particular, we prove that c(C ₄)=1, which is best possible.     

The strong metric dimension of graphs and digraphs

Let G be a connected (di)graph. A vertex w is said to strongly resolve a pair u,v of vertices of G if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set W of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of W. The smallest cardinality of a strong resolving set for G is called the strong dimension of G. It is shown that the problem of finding the strong dimension of a connected graph can be transformed to the problem of finding the vertex covering number of a graph. Moreover, it is shown that computing this invariant is NP-hard. Related invariants for directed graphs are defined and studied.     

Connected Resolvability of Graphs

For an ordered set W = {w ₁, w ₂,..., w _k} of vertices and a vertex v in a connected graph G, the representation of v with respect to W is the k-vector r(v|W) = (d(v, w ₁), d(v, w ₂),... d(v, w _k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations with respect to W. A resolving set for G containing a minimum number of vertices is a basis for G. The dimension dim(G) is the number of vertices in a basis for G. A resolving set W of G is connected if the subgraph 〈W〉 induced by W is a nontrivial connected subgraph of G. The minimum cardinality of a connected resolving set in a graph G is its connected resolving number cr(G). Thus 1 ≤ dim(G) ≤ cr(G) ≤ n?1 for every connected graph G of order n ≥ 3. The connected resolving numbers of some well-known graphs are determined. It is shown that if G is a connected graph of order n ≥ 3, then cr(G) = n?1 if and only if G = K _n or G = K _1,n?1. It is also shown that for positive integers a, b with a ≤ b, there exists a connected graph G with dim(G) = a and cr(G) = b if and only if $\left( {a,b} \right) \notin \left\{ {\left( {1,k} \right):k = 1\;{\text{or}}\;k \geqslant 3} \right\}$ Several other realization results are present. The connected resolving numbers of the Cartesian products G × K ₂ for connected graphs G are studied.     

On the number of noncritical vertices in strongly connected digraphs

By definition, a vertex w of a strongly connected (or, simply, strong) digraph D is noncritical if the subgraph D — w is also strongly connected. We prove that if the minimal out (or in) degree k of D is at least 2, then there are at least k noncritical vertices in D. In contrast to the case of undirected graphs, this bound cannot be sharpened, for a given k, even for digraphs of large order. Moreover, we show that if the valency of any vertex of a strong digraph of order n is at least 3/4n, then it contains at least two noncritical vertices. The proof makes use of the results of the theory of maximal proper strong subgraphs established by Mader and developed by the present author. We also construct a counterpart of this theory for biconnected (undirected) graphs.     

Occupation games on graphs in which the second player takes almost all vertices

Given a connected graph G=(V,E), two players take turns occupying vertices v∈V by placing black and white tokens so that the current vertex sets B,W⊆V are disjoint, B∩W=0?, and the corresponding induced subgraphs G[B] and G[W] are connected any time. A player must pass whenever (s)he has no legal move. (Obviously, after this, the opponent will take all remaining vertices, since G is assumed connected.) The game is over when all vertices are taken, V=B^∗∪W^∗. Then, Black and White get b=|B^∗|/|V| and w=|W^∗|/|V|, respectively. Thus, the occupation game is one-sum, b+w=1, and we could easily reduce it to a zero-sum game by simply shifting the payoffs, b^′=b−1/2,w^′=w−1/2. Let us also notice that b≥0 and w≥0; moreover, b>0 and w>0 whenever |V|>1.[Let us remark that the so-called Chinese rules define similar payoffs for the classic game of GO, yet, the legal moves are defined in GO differently.]Like in GO, we assume that Black begins. It is easy to construct graphs in which Black can take almost all vertices, more precisely, for each ε>0 there is a graph G for which b>1−ε. In this paper we show that, somewhat surprisingly, there are also graphs in which White can take almost all vertices.     

Free Choosability of Outerplanar Graphs

A graph G is free (a, b)-choosable if for any vertex v with b colors assigned and for any list of colors of size a associated with each vertex \(u\ne v\), the coloring can be completed by choosing for u a subset of b colors such that adjacent vertices are colored with disjoint color sets. In this note, a necessary and sufficient condition for a cycle to be free (a, b)-choosable is given. As a corollary, we obtain almost optimal results about the free (a, b)-choosability of outerplanar graphs.     

Injective colorings of planar graphs with few colors

An injective coloring of a graph is a vertex coloring where two vertices have distinct colors if a path of length two exists between them. In this paper some results on injective colorings of planar graphs with few colors are presented. We show that all planar graphs of girth ≥ 19 and maximum degree Δ are injectively Δ-colorable. We also show that all planar graphs of girth ≥ 10 are injectively (Δ+1)-colorable, that Δ+4 colors are sufficient for planar graphs of girth ≥ 5 if Δ is large enough, and that subcubic planar graphs of girth ≥ 7 are injectively 5-colorable.     

Equitable list coloring and treewidth

Given lists of available colors assigned to the vertices of a graph G, a list coloring is a proper coloring of G such that the color on each vertex is chosen from its list. If the lists all have size k, then a list coloring is equitable if each color appears on at most ?|V(G)|/k? vertices. A graph is equitably k ‐choosable if such a coloring exists whenever the lists all have size k. Kostochka, Pelsmajer, and West introduced this notion and conjectured that G is equitably k‐choosable for k>Δ(G). We prove this for graphs of treewidth w≤5 if also k≥3w?1. We also show that if G has treewidth w≥5, then G is equitably k‐choosable for k≥max{Δ(G)+w?4, 3w?1}. As a corollary, if G is chordal, then G is equitably k‐choosable for k≥3Δ(G)?4 when Δ(G)>2. © 2009 Wiley Periodicals, Inc. J Graph Theory     

The deficiency of a regular graph

A proper edge coloring c:E(G)→Z of a finite simple graph G is an interval coloring if the colors used at each vertex form a consecutive interval of integers. Many graphs do not have interval colorings, and the deficiency of a graph is an invariant that measures how close a graph comes to having an interval coloring. In this paper we search for tight upper bounds on the deficiencies of k-regular graphs in terms of the number of vertices. We find exact values for 1?k?4 and bounds for larger k.     

A characterization of well-covered graphs that contain neither 4- nor 5-cycles

A graph is well covered if every maximal independent set has the same cardinality. A vertex x, in a well-covered graph G, is called extendable if G – {x} is well covered and β(G) = β(G – {x}). If G is a connected, well-covered graph containing no 4- nor 5-cycles as subgraphs and G contains an extendable vertex, then G is the disjoint union of edges and triangles together with a restricted set of edges joining extendable vertices. There are only 3 other connected, well-covered graphs of this type that do not contain an extendable vertex. Moreover, all these graphs can be recognized in polynomial time.     

Distance-residual subgraphs

For a connected finite graph G and a subset V₀ of its vertex set, a distance-residual subgraph is a subgraph induced on the set of vertices at the maximal distance from V₀. Some properties and examples of distance-residual subgraphs of vertex-transitive, edge-transitive, bipartite and semisymmetric graphs are presented. The relations between the distance-residual subgraphs of product graphs and their factors are explored.     

Ramsey‐type results for Gallai colorings

A Gallai‐coloring of a complete graph is an edge coloring such that no triangle is colored with three distinct colors. Gallai‐colorings occur in various contexts such as the theory of partially ordered sets (in Gallai's original paper) or information theory. Gallai‐colorings extend 2‐colorings of the edges of complete graphs. They actually turn out to be close to 2‐colorings—without being trivial extensions. Here, we give a method to extend some results on 2‐colorings to Gallai‐colorings, among them known and new, easy and difficult results. The method works for Gallai‐extendible families that include, for example, double stars and graphs of diameter at most d for 2?d, or complete bipartite graphs. It follows that every Gallai‐colored K_n contains a monochromatic double star with at least 3n+ 1/4 vertices, a monochromatic complete bipartite graph on at least n/2 vertices, monochromatic subgraphs of diameter two with at least 3n/4 vertices, etc. The generalizations are not automatic though, for instance, a Gallai‐colored complete graph does not necessarily contain a monochromatic star on n/2 vertices. It turns out that the extension is possible for graph classes closed under a simple operation called equalization. We also investigate Ramsey numbers of graphs in Gallai‐colorings with a given number of colors. For any graph H let RG(r, H) be the minimum m such that in every Gallai‐coloring of K_m with r colors, there is a monochromatic copy of H. We show that for fixed H, RG (r, H) is exponential in r if H is not bipartite; linear in r if H is bipartite but not a star; constant (does not depend on r) if H is a star (and we determine its value). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 233–243, 2010