Edge coloring of graphs with small maximum degrees

By applying a discharging method, we give new lower bounds for the sizes of edge chromatic critical graphs for small maximum degrees. Furthermore, it is also proved that if G is a graph embeddable in a surface S with characteristic c_S=−4 or −5 or −6, then G is class one if its maximum degree Δ≥10 or 11 or 12 respectively.     

Edge-coloring critical graphs with high degree

It is proved here that any edge-coloring critical graph of order n and maximum degree Δ?8 has the size at least 3(n+Δ−8). It generalizes a result of Hugh Hind and Yue Zhao.     

Edge covered critical multigraphs

Let G be a multigraph with edge set E(G). An edge coloring C of G is called an edge covered coloring, if each color appears at least once at each vertex v∈V(G). The maximum positive integer k such that G has a k edge covered coloring is called the edge covered chromatic index of G and is denoted by . A graph G is said to be of class if and otherwise of class. A pair of vertices {u,v} is said to be critical if . A graph G is said to be edge covered critical if it is of class and every edge with vertices in V(G) not belonging to E(G) is critical. Some properties about edge covered critical graphs are considered.     

Cycle-magic graphs

A simple graph G=(V,E) admits a cycle-covering if every edge in E belongs at least to one subgraph of G isomorphic to a given cycle C. Then the graph G is C-magic if there exists a total labelling f:V∪E→{1,2,…,|V|+|E|} such that, for every subgraph H^′=(V^′,E^′) of G isomorphic to C, ∑_v∈V^′f(v)+∑_e∈E^′f(e) is constant. When f(V)={1,…,|V|}, then G is said to be C-supermagic.We study the cyclic-magic and cyclic-supermagic behavior of several classes of connected graphs. We give several families of C_r-magic graphs for each r?3. The results rely on a technique of partitioning sets of integers with special properties.     

On some three color Ramsey numbers for paths and cycles

For given graphs G₁,G₂,…,G_k, k≥2, the multicolor Ramsey number, denoted by R(G₁,G₂,…,G_k), is the smallest integer n such that if we arbitrarily color the edges of a complete graph on n vertices with k colors, there is always a monochromatic copy of G_i colored with i, for some 1≤i≤k. Let P_k (resp. C_k) be the path (resp. cycle) on k vertices. In the paper we consider the value for numbers of type R(P_i,P_k,C_m) for odd m, k≥m≥3 and when i is odd, and when i is even. In addition, we provide the exact values for Ramsey numbers R(P₃,P_k,C₄) for all integers k≥3.     

Semi-hyper-connected edge transitive graphs

A graph G is said to be hyper-connected if the removal of every minimum cut creates exactly two connected components, one of which is an isolated vertex. In this paper, we first generalize the concept of hyper-connected graphs to that of semi-hyper-connected graphs: a graph G is called semi-hyper-connected if the removal of every minimum cut of G creates exactly two components. Then we characterize semi-hyper-connected edge transitive graphs.     

Some results in square-free and strong square-free edge-colorings of graphs

The set of problems we consider here are generalizations of square-free sequences [A. Thue, Über unendliche Zeichenreichen, Norske Vid Selsk. Skr. I. Mat. Nat. Kl. Christiana 7 (1906) 1-22]. A finite sequence a₁a₂…a_n of symbols from a set S is called square-free if it does not contain a sequence of the form ww=x₁x₂…x_mx₁x₂…x_m,x_i∈S, as a subsequence of consecutive terms. Extending the above concept to graphs, a coloring of the edge set E in a graph G(V,E) is called square-free if the sequence of colors on any path in G is square-free. This was introduced by Alon et al. [N. Alon, J. Grytczuk, M. Ha?uszczak, O. Riordan, Nonrepetitive colorings of graphs, Random Struct. Algor. 21 (2002) 336-346] who proved bounds on the minimum number of colors needed for a square-free edge-coloring of G on the class of graphs with bounded maximum degree and trees. We discuss several variations of this problem and give a few new bounds.     

Edge colouring by total labellings

We introduce the concept of an edge-colouring total k-labelling. This is a labelling of the vertices and the edges of a graph G with labels 1,2,…,k such that the weights of the edges define a proper edge colouring of G. Here the weight of an edge is the sum of its label and the labels of its two endvertices. We define to be the smallest integer k for which G has an edge-colouring total k-labelling. This parameter has natural upper and lower bounds in terms of the maximum degree Δ of . We improve the upper bound by 1 for every graph and prove . Moreover, we investigate some special classes of graphs.     

On randomized broadcasting in Star graphs

One of the most frequently studied problems in the context of information dissemination in communication networks is the broadcasting problem. In this paper, we study the following robust, simple, and scalable randomized broadcasting protocol: at some time t an information is placed at one of the nodes of a graph G, and in the succeeding steps, each informed node chooses one of its neighbours in G uniformly at random, and sends the information to this neighbour.We show that this algorithm spreads an information to all nodes in a Star graph S_n of dimension n within O(logN) steps, with high probability, where N denotes the number of nodes in S_n. To obtain this result, we first establish lower bounds on the edge expansion of small subsets of nodes. Then we introduce a simple but powerful technique for estimating the runtime of randomized broadcasting by analyzing the protocol described above in the reverse order. Using this technique we can also simplify the analysis of this algorithm in Hypercubes [U. Feige, D. Peleg, P. Raghavan, E. Upfal, Randomized broadcast in networks, Random Structures and Algorithms 1 (4) (1990) 447-460].     

A note on the edge cover chromatic index of multigraphs

Let G be a multigraph with vertex set V(G). An edge coloring C of G is called an edge-cover-coloring if each color appears at least once at each vertex v∈V(G). The maximum positive integer k such that G has a k-edge-cover-coloring is called the edge cover chromatic index of G and is denoted by . It is well known that , where μ(v) is the multiplicity of v and δ(G) is the minimum degree of G. We improve this lower bound to δ(G)−1 when 2≤δ(G)≤5. Furthermore we show that this lower bound is best possible.     

A bound on the total size of a cut cover

A cycle cover (cut cover) of a graph G is a collection of cycles (cuts) of G that covers every edge of G at least once. The total size of a cycle cover (cut cover) is the sum of the number of edges of the cycles (cuts) in the cover.We discuss several results for cycle covers and the corresponding results for cut covers. Our main result is that every connected graph on n vertices and e edges has a cut cover of total size at most 2e-n+1 with equality precisely when every block of the graph is an odd cycle or a complete graph (other than K₄ or K₈). This corresponds to the result of Fan [J. Combin. Theory Ser. B 74 (1998) 353-367] that every graph without cut-edges has a cycle cover of total size at most e+n-1.     

The depression of a graph and the diameter of its line graph

An edge ordering of a graph G=(V,E) is an injection f:E→Q⁺ where Q⁺ is the set of positive rational numbers. A (simple) path λ for which f increases along its edge sequence is an f-ascent, and a maximal f-ascent if it is not contained in a longer f-ascent. The depression ε(G) of G is the least integer k such that every edge ordering of G has a maximal ascent of length at most k.It has been shown in [E.J. Cockayne, G. Geldenhuys, P.J.P. Grobler, C.M. Mynhardt, J. van Vuuren, The depression of a graph, Utilitas Math. 69 (2006) 143-160] that the difference may be made arbitrarily large. We prove that the difference can also be arbitrarily large, thus answering a question raised in [E.J. Cockayne, G. Geldenhuys, P.J.P. Grobler, C.M. Mynhardt, J. van Vuuren, The depression of a graph, Utilitas Math. 69 (2006) 143-160].     

Vertex-minor reductions can simulate edge contractions

We prove that local complementation and vertex deletion, operations from which vertex-minors are defined, can simulate edge contractions. As an application, we prove that the rank-width of a graph is linearly bounded in term of its tree-width.     

Structural properties and edge choosability of planar graphs without 4-cycles

Some structural properties of planar graphs without 4-cycles are investigated. By the structural properties, it is proved that every planar graph G without 4-cycles is edge-(Δ(G)+1)-choosable, which perfects the result given by Zhang and Wu: If G is a planar graph without 4-cycles, then G is edge-t-choosable, where t=7 if Δ(G)=5, and otherwise t=Δ(G)+1.     

Edge decompositions into two kinds of graphs

Let H be an arbitrary graph and let K_1,2 be the 2-edge star. By a {K_1,2,H}-decomposition of a graph G we mean a partition of the edge set of G into subsets inducing subgraphs isomorphic to K_1,2 or H. Let J be an arbitrary connected graph of odd size. We show that the problem to decide if an instance graph G has a {K_1,2,H}-decomposition is NP-complete if H has a component of an odd size and H≠pK_1,2∪qJ, where pK_1,2∪qJ is the disjoint union of p copies of K_1,2 and q copies of J. Moreover, we prove polynomiality of this problem for H=qJ.     

Super-connected edge transitive graphs

A graph G is said to be super-connected if any minimum cut of G isolates a vertex. In a previous work due to the second author of this note, super-connected graphs which are both vertex transitive and edge transitive are characterized. In this note, we generalize the characterization to edge transitive graphs which are not necessarily vertex transitive, showing that the only irreducible edge transitive graphs which are not super-connected are the cycles C_n(n?6) and the line graph of the 3-cube, where irreducible means the graph has no vertices with the same neighbor set. Furthermore, we give some sufficient conditions for reducible edge transitive graphs to be super-connected.     

Distinguishing colorings of Cartesian products of complete graphs

We determine the values of s and t for which there is a coloring of the edges of the complete bipartite graph K_s,t which admits only the identity automorphism. In particular, this allows us to determine the distinguishing number of the Cartesian product of complete graphs.     

Light graphs in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight

A graph H is defined to be light in a family H of graphs if there exists a finite number φ(H,H) such that each G∈H which contains H as a subgraph, contains also a subgraph K≅H such that the Δ_G(K)≤φ(H,H). We study light graphs in families of polyhedral graphs with prescribed minimum vertex degree δ, minimum face degree ρ, minimum edge weight w and dual edge weight w^∗. For those families, we show that there exists a variety of small light cycles; on the other hand, we also present particular constructions showing that, for certain families, the spectrum of short cycles contains irregularly scattered cycles that are not light.     

On covering graphs by complete bipartite subgraphs

We prove that, if a graph with e edges contains m vertex-disjoint edges, then m²/e complete bipartite subgraphs are necessary to cover all its edges. Similar lower bounds are also proved for fractional covers. For sparse graphs, this improves the well-known fooling set lower bound in communication complexity. We also formulate several open problems about covering problems for graphs whose solution would have important consequences in the complexity theory of boolean functions.     

Some sufficient conditions for a planar graph of maximum degree six to be Class 1

Let G be a planar graph of maximum degree 6. In this paper we prove that if G does not contain either a 6-cycle, or a 4-cycle with a chord, or a 5- and 6-cycle with a chord, then χ^′(G)=6, where χ^′(G) denotes the chromatic index of G.