Neighbor sum distinguishing colorings of graphs with maximum average degree less than $$\tfrac{{37}} {{12}}$$

Let G be a graph and let its maximum degree and maximum average degree be denoted by Δ(G) and mad(G), respectively. A neighbor sum distinguishing k-edge colorings of graph G is a proper k-edge coloring of graph G such that, for any edge uv ∈ E(G), the sum of colors assigned on incident edges of u is different from the sum of colors assigned on incident edges of v. The smallest value of k in such a coloring of G is denoted by χ′_∑(G). Flandrin et al. proposed the following conjecture that χ′_∑ (G) ≤ Δ(G) + 2 for any connected graph with at least 3 vertices and G ≠ C₅. In this paper, we prove that the conjecture holds for a normal graph with mad(G) < \(\tfrac{{37}}{{12}}\) and Δ(G) ≥ 7.     

Edge‐colorings avoiding rainbow stars

We consider an extremal problem motivated by a article of Balogh [J. Balogh, A remark on the number of edge colorings of graphs, European Journal of Combinatorics 27, 2006, 565–573], who considered edge‐colorings of graphs avoiding fixed subgraphs with a prescribed coloring. More precisely, given , we look for n‐vertex graphs that admit the maximum number of r‐edge‐colorings such that at most colors appear in edges incident with each vertex, that is, r‐edge‐colorings avoiding rainbow‐colored stars with t edges. For large n, we show that, with the exception of the case , the complete graph is always the unique extremal graph. We also consider generalizations of this problem.     

Size of monochromatic components in local edge colorings

An edge coloring of a graph is a local r coloring if the edges incident to any vertex are colored with at most r distinct colors. We determine the size of the largest monochromatic component that must occur in any local r coloring of a complete graph or a complete bipartite graph.     

Spreads in Strongly Regular Graphs

A spread of a strongly regular graph is a partitionof the vertex set into cliques that meet Delsarte's bound (alsocalled Hoffman's bound). Such spreads give rise to coloringsmeeting Hoffman's lower bound for the chromatic number and tocertain imprimitive three-class association schemes. These correspondenceslead to conditions for existence. Most examples come from spreadsand fans in (partial) geometries. We give other examples, includinga spread in the McLaughlin graph. For strongly regular graphsrelated to regular two-graphs, spreads give lower bounds forthe number of non-isomorphic strongly regular graphs in the switchingclass of the regular two-graph.     

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.     

ContributionsEdge colorings of graphs embeddable in a surface of low genus

In this paper, by using the Discharging Method, we show that any graph with maximum degree Δ 8 that is embeddable in a surface Σ of characteristic χ(Σ) 0 is class one and any graph with maximum degree Δ 9 that is embeddable in a surface Σ of characteristic χ(Σ) = − 1 is class one. For surfaces of characteristic 0 or −1, these results improve earlier results of Mel'nikov.     

Tiles and Colors

Tiling models are classical statistical models in which different geometric shapes, the tiles, are packed together such that they cover space completely. In this paper we discuss a class of two-dimensional tiling models in which the tiles are rectangles and isosceles triangles. Some of these models have been solved recently by means of Bethe Ansatz. We discuss the question why only these models in a larger family are solvable, and we search for the Yang–Baxter structure behind their integrability. In this quest we find the Bethe Ansatz solution of the problem of coloring the edges of the square lattice in four colors, such that edges of the same color never meet in the same vertex.     

Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree

A proper [h]-total coloring c of a graph G is a proper total coloring c of G using colors of the set [h]={1,2,...,h}.Letw(u) denote the sum of the color on a vertex u and colors on all the edges incident to u.For each edge uv∈E(G),if w(u)≠w(v),then we say the coloring c distinguishes adjacent vertices by sum and call it a neighbor sum distinguishing [h]-total coloring of G.By tndi(G),we denote the smallest value h in such a coloring of G.In this paper,we obtain that G is a graph with at least two vertices,if mad(G)3,then tndi∑(G)≤k+2 where k=max{Δ(G),5}.It partially con?rms the conjecture proposed by Pil′sniak and Wozniak.     

Inequalities for the Grundy chromatic number of graphs

The Grundy (or First-Fit) chromatic number of a graph G is the maximum number of colors used by the First-Fit coloring of the graph G. In this paper we give upper bounds for the Grundy number of graphs in terms of vertex degrees, girth, clique partition number and for the line graphs. Next we show that if the Grundy number of a graph is large enough then the graph contains a subgraph of prescribed large girth and Grundy number.     

Cyclic 4‐Colorings of Graphs on Surfaces

To attack the Four Color Problem, in 1880, Tait gave a necessary and sufficient condition for plane triangulations to have a proper 4‐vertex‐coloring: a plane triangulation G has a proper 4‐vertex‐coloring if and only if the dual of G has a proper 3‐edge‐coloring. A cyclic coloring of a map G on a surface F² is a vertex‐coloring of G such that any two vertices x and y receive different colors if x and y are incident with a common face of G. In this article, we extend the result by Tait to two directions, that is, considering maps on a nonspherical surface and cyclic 4‐colorings.