An extension of bipartite multigraphs

Usual edge colorings have been generalized in various ways; we will consider here essentially good edge colorings as well as equitable edge colorings. It is known that bipartite multigraphs present the property of having an equitable k-coloring for each k ? 2. This implies that they also have a good k-coloring for each k ? 2. In this paper, we characterize a class of multigraphs which may be considered as a generalization of bipartite multigraphs, in the sense that for each k ? 2 they have a good k-coloring. A more restrictive class is derived where all multigraphs have an equitable k-coloring for each k ? 2.     

Thue type problems for graphs, points, and numbers

A sequence S=s₁s₂…s_n is said to be nonrepetitive if no two adjacent blocks of S are the same. A celebrated 1906 theorem of Thue asserts that there are arbitrarily long nonrepetitive sequences over the set {0,1,2}. This result is the starting point of Combinatorics on Words—a wide area with many deep results, sophisticated methods, important applications and intriguing open problems.The main purpose of this survey is to present a range of new directions relating Thue sequences more closely to Graph Theory, Combinatorial Geometry, and Number Theory. For instance, one may consider graph colorings avoiding repetitions on paths, or colorings of points in the plane avoiding repetitions on straight lines. Besides presenting a variety of new challenges we also recall some older problems of this area.     

No-hole 2-distant colorings for Cayley graphs on finitely generated abelian groups

A no-hole 2-distant coloring of a graph Γ is an assignment c of nonnegative integers to the vertices of Γ such that |c(v)-c(w)|?2 for any two adjacent vertices v and w, and the integers used are consecutive. Whenever such a coloring exists, define nsp(Γ) to be the minimum difference (over all c) between the largest and smallest integers used. In this paper we study the no-hole 2-distant coloring problem for Cayley graphs over finitely generated abelian groups. We give sufficient conditions for the existence of no-hole 2-distant colorings of such graphs, and obtain upper bounds for the minimum span nsp(Γ) by using a group-theoretic approach.     

On resistance of graphs

An edge-coloring of a graph G with integers is called an interval coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. It is known that not all graphs have interval colorings, and therefore it is expedient to consider a measure of closeness for a graph to be interval colorable. In this paper we introduce such a measure (resistance of a graph) and we determine the exact value of the resistance for some classes of graphs.     

Triple point cancelling numbers of surface links and quandle cocycle invariants

The unknotting or triple point cancelling number of a surface link F is the least number of 1-handles for F such that the 2-knot obtained from F by surgery along them is unknotted or pseudo-ribbon, respectively. These numbers have been often studied by knot groups and Alexander invariants. On the other hand, quandle colorings and quandle cocycle invariants of surface links were introduced and applied to other aspects, including non-invertibility and triple point numbers. In this paper, we give lower bounds of the unknotting or triple point cancelling numbers of surface links by using quandle colorings and quandle cocycle invariants.     

Orientable edge colorings of graphs

An edge coloring of a graph is orientable if and only if it is possible to orient the edges of the graph so that the color of each edge is determined by the head of its corresponding oriented arc. The goals of this paper include finding a forbidden substructure characterization of orientable colorings and giving a linear time recognition algorithm for orientable colorings.An edge coloring is lexical if and only if it is possible to number the vertices of the graph so that the color of each edge is determined by its lower endpoint. Lexical colorings are, of course, the orientable colorings in which the underlying orientation is acyclic. Lexical colorings play an important role in Canonical Ramsey theory, and it is this standpoint that motivates the current study.     

A problem ? multi-colorings of graphs

In this paper we consider colorings of the edges of the complete graph K_m with n colors such that the edges of any color form a non-trivial complete subgraph of K_m. We allow an edge of K_m to have more than one color. Such a coloring will be called r-admissible if no cycle of length r has a different color for each edge. Let E (m, n, r) be the maximum number of incidences of colors and edges, taken over all r-admissible colorings of K_m with n colors. Then for r = 3,4, and 5 we give an upper bound for E (m, n, r); as well as a lower bound for E (m, n, r) for all r. An analogue to a problem of Zarankiewicz concerning 0, 1-matrices is mentioned.     

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     

The edge chromatic number of a directed/mixed multigraph

We consider colorings of the directed and undirected edges of a mixed multigraph G by an ordered set of colors. We color each undirected edge in one color and each directed edge in two colors, such that the color of the first half of a directed edge is smaller than the color of the second half. The colors used at the same vertex are all different. A bound for the minimum number of colors needed for such colorings is obtained. In the case where G has only directed edges, we provide a polynomal algorithm for coloring G with a minimum number of colors. An unsolved problem is formulated. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 267–273, 1999     

A Reduction of the Anticoloring Problem to Connected Graphs

An anticoloring of a graph is a coloring of some of the vertices, such that no two adjacent vertices are colored in distinct colors. The anticoloring problem seeks, roughly speaking, for such colorings with many vertices colored in each color. We show that, to solve the anticoloring problem with two colors for general graphs, it suffices to solve it for connected graphs.     

Hajós Theorem For Colorings Of Edge-Weighted Graphs

Hajós theorem states that every graph with chromatic number at least k can be obtained from the complete graph K _k by a sequence of simple operations such that every intermediate graph also has chromatic number at least k. Here, Hajós theorem is extended in three slightly different ways to colorings and circular colorings of edge-weighted graphs. These extensions shed some new light on the Hajós theorem and show that colorings of edge-weighted graphs are most natural extension of usual graph colorings.* Supported in part by the Ministry of Education, Science and Sport of Slovenia, Research Program P0–0507–0101.     

Disconnected Colors in Generalized Gallai‐Colorings

Gallai‐colorings of complete graphs—edge colorings such that no triangle is colored with three distinct colors—occur in various contexts such as the theory of partially ordered sets (in Gallai's original paper), information theory and the theory of perfect graphs. A basic property of Gallai‐colorings with at least three colors is that at least one of the color classes must span a disconnected graph. We are interested here in whether this or a similar property remains true if we consider colorings that do not contain a rainbow copy of a fixed graph F. We show that such graphs F are very close to bipartite graphs, namely, they can be made bipartite by the removal of at most one edge. We also extend Gallai's property for two infinite families and show that it also holds when F is a path with at most six vertices.     

Basis theorems for continuous n-colorings

This article is devoted to the study of continuous colorings of the n-element subsets of a Polish space.The homogeneity numberhm(c) of an n-coloring c:n[X]→2 is the least size of a family of c-homogeneous sets that covers X. An n-coloring is uncountably homogeneous if hm(c)>ℵ₀. Answering a question of B. Miller, we show that for every n>1 there is a finite family B of continuous n-colorings on ω² such that every uncountably homogeneous, continuous n-coloring on a Polish space contains a copy of one of the colorings from B. We also give upper and lower bounds for the minimal size of such a basisB.     

d-strong Edge Colorings of Graphs

For a proper edge coloring of a graph G the palette S(v) of a vertex v is the set of the colors of the incident edges. If S(u) ≠ S(v) then the two vertices u and v of G are distinguished by the coloring. A d-strong edge coloring of G is a proper edge coloring that distinguishes all pairs of vertices u and v with distance 1 ≤ d (u, v) ≤ d. The d-strong chromatic index ${\chi_{d}^{\prime}(G)}$ of G is the minimum number of colors of a d-strong edge coloring of G. Such colorings generalize strong edge colorings and adjacent strong edge colorings as well. We prove some general bounds for ${\chi_{d}^{\prime}(G)}$ , determine ${\chi_{d}^{\prime}(G)}$ completely for paths and give exact values for cycles disproving a general conjecture of Zhang et al. (Acta Math Sinica Chin Ser 49:703–708 2006)).     

D(β)-vertex-distinguishing total coloring of graphs

A new concept of the D(β)-vertex-distinguishing total coloring of graphs, i.e., the proper total coloring such that any two vertices whose distance is not larger than β have different color sets, where the color set of a vertex is the set composed of all colors of the vertex and the edges incident to it, is proposed in this paper. The D(2)-vertex-distinguishing total colorings of some special graphs are discussed, meanwhile, a conjecture and an open problem are presented.     

On d-diagonal colorings

A coloring of a graph embedded on a surface is d-diagonal if any pair of vertices that are in the same face after the deletion of at most d edges of the graph must be colored differently. Hornak and Jendrol introduced d-diagonal colorings as a generalization of cyclic colorings and diagonal colorings. This paper proves a conjecture of Hornak and Jendrol that plane quadrangulations have d-diagonal colorings with at most 1 + 2 · 3^d+1 colors. A similar result is proven for plane triangulations. Each of these results extends to the projective plane. Also, a lower bound for the d-diagonal chromatic number is given. © 1996 John Wiley & Sons, Inc.     

Acyclic improper choosability of graphs

We consider improper colorings (sometimes called generalized, defective or relaxed colorings) in which every color class has a bounded degree. We propose a natural extension of improper colorings: acyclic improper choosability. We prove that subcubic graphs are acyclically (3, 1)*-choosable (i.e. they are acyclically 3-choosable with color classes of maximum degree one). Using a linear time algorithm, we also prove that outerplanar graphs are acyclically (2, 5)*-choosable (i.e. they are acyclically 2-choosable with color classes of maximum degree five). Both results are optimal. We finally prove that acyclic choosability and acyclic improper choosability of planar graphs are equivalent notions.     

On the equality of the partial Grundy and upper ochromatic numbers of graphs

A (proper) k-coloring of a graph G is a partition Π={V₁,V₂,…,V_k} of V(G) into k independent sets, called color classes. In a k-coloring Π, a vertex v∈V_i is called a Grundy vertex if v is adjacent to at least one vertex in color class V_j, for every j, j<i. A k-coloring is called a Grundy coloring if every vertex is a Grundy vertex. A k-coloring is called a partial Grundy coloring if every color class contains at least one Grundy vertex. In this paper we introduce partial Grundy colorings, and relate them to parsimonious proper colorings introduced by Simmons in 1982.