a journal of mathematics msp Clique-relaxed graph coloring

Acyclic (Δ + 2)-Edge Coloring of Toroidal Graphs Without Short Cycles

An acyclic edge coloring of a graph G is a proper edge coloring such that G contains no bichromatic cycles. The acyclic chromatic index χa′(G) is the minimum number of colors required for an acyclic edge coloring. Fiamčik and Alon et al. independently conjectured that χa′(G)≤Δ+2 for every simple graph G with maximum de...

Equitable Chromatic Numbers of Derived Graph of Particular Graphs.

An equitable k-coloring is a proper coloring with color classes V_1,V_2,\ldots,V_{k} for which the numbers of vertices in any two color classes differ by at most one. A graph G is equitably k-colorable if there is an equitable k-coloring. The smallest positive integer k such that G is equitably k-colorable is the equit...

(In)tractability of the maximum 2 -clique problem for bipartite graphs

The r-Hued Coloring of Complements of Cycles

Given a graph G , an r -hued coloring of G is a proper vertex coloring such that for every vertex v , the number of colors appearing in its neighborhood is at least min { d G ( v ) , r } , where d G ( v ) denotes the degree of v in G . The r -hued chromatic number χ r ( G ) is the smallest number of colors needed for a...

Sequence b-colorings in graphs

We introduce and begin the study of sequence b-colorings, a natural generalization of the classical notion of b-colorings introduced by Irving and Manlove in 1999. In a sequence b-coloring, each color class is required to contain a prescribed minimum number of color-dominating vertices (CDVs). We establish several fund...

On 3-Distance Independent Sets of Graphs.

Let G be a graph with vertex set V(G) and edge set E(G). A set S \subseteq V(G) is a 3-distance independent set of G if d_G(v,w) \neq 3 for any two distinct vertices v,w \in S. The maximum cardinality of a 3-distance independent set of G, denoted by \alpha^3(G), is called the 3-distance independence number of G. In thi...