List coloring of Cartesian products of graphs

A well-established generalization of graph coloring is the concept of list coloring. In this setting, each vertex v of a graph G is assigned a list L(v) of k colors and the goal is to find a proper coloring c of G with c(v)∈L(v). The smallest integer k for which such a coloring c exists for every choice of lists is called the list chromatic number of G and denoted by χ_l(G).We study list colorings of Cartesian products of graphs. We show that unlike in the case of ordinary colorings, the list chromatic number of the product of two graphs G and H is not bounded by the maximum of χ_l(G) and χ_l(H). On the other hand, we prove that χ_l(G×H)?min{χ_l(G)+col(H),col(G)+χ_l(H)}-1 and construct examples of graphs G and H for which our bound is tight.     

Colorings at minimum cost

We define by min_c∑_{u,v}∈E(G)|c(u)−c(v)| the min-costMC(G) of a graph G, where the minimum is taken over all proper colorings c. The min-cost-chromatic numberχ_M(G) is then defined to be the (smallest) number of colors k for which there exists a proper k-coloring c attaining MC(G). We give constructions of graphs G where χ(G) is arbitrarily smaller than χ_M(G). On the other hand, we prove that for every 3-regular graph G^′, χ_M(G^′)≤4 and for every 4-regular line graph G^″, χ_M(G^″)≤5. Moreover, we show that the decision problem whether χ_M(G)=k is -hard for k≥3.     

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)).     

On hamiltonian colorings for some graphs

For a connected graph G and any two vertices u and v in G, let D(u,v) denote the length of a longest u-v path in G. A hamiltonian coloring of a connected graph G of order n is an assignment c of colors (positive integers) to the vertices of G such that |c(u)−c(v)|+D(u,v)≥n−1 for every two distinct vertices u and v in G. The value of a hamiltonian coloring c is the maximum color assigned to a vertex of G. The hamiltonian chromatic number of G is taken over all hamiltonian colorings c of G. In this paper we discuss the hamiltonian chromatic number of graphs G with . As examples, we determine the hamiltonian chromatic number for a class of caterpillars, and double stars.     

On the locating chromatic number of Kneser graphs

Let c be a proper k-coloring of a connected graph G and Π=(C₁,C₂,…,C_k) be an ordered partition of V(G) into the resulting color classes. For a vertex v of G, the color code of v with respect to Π is defined to be the ordered k-tuple c_Π(v):=(d(v,C₁),d(v,C₂),…,d(v,C_k)), where d(v,C_i)=min{d(v,x)|x∈C_i},1≤i≤k. If distinct vertices have distinct color codes, then c is called a locating coloring. The minimum number of colors needed in a locating coloring of G is the locating chromatic number of G, denoted by χ_L(G). In this paper, we study the locating chromatic number of Kneser graphs. First, among some other results, we show that χ_L(KG(n,2))=n−1 for all n≥5. Then, we prove that χ_L(KG(n,k))≤n−1, when n≥k². Moreover, we present some bounds for the locating chromatic number of odd graphs.     

deBruijn-like sequences and the irregular chromatic number of paths and cycles

A deBruijn sequence of orderk, or a k-deBruijn sequence, over an alphabet A is a sequence of length |A|^k in which the last element is considered adjacent to the first and every possible k-tuple from A appears exactly once as a string of k-consecutive elements in the sequence. We will say that a cyclic sequence is deBruijn-like if for some k, each of the consecutive k-element substrings is distinct.A vertex coloring χ:V(G)→[k] of a graph G is said to be proper if no pair of adjacent vertices in G receive the same color. Let C(v;χ) denote the multiset of colors assigned by a coloring χ to the neighbors of vertex v. A proper coloring χ of G is irregular if χ(u)=χ(v) implies that C(u;χ)≠C(v;χ). The minimum number of colors needed to irregularly color G is called the irregular chromatic number of G. The notion of the irregular chromatic number pairs nicely with other parameters aimed at distinguishing the vertices of a graph. In this paper, we demonstrate a connection between the irregular chromatic number of cycles and the existence of certain deBruijn-like sequences. We then determine the exact irregular chromatic number of C_n and P_n for n≥3, thus verifying two conjectures given by Okamoto, Radcliffe and Zhang.     

Set vertex colorings and joins of graphs

For a nontrivial connected graph G, let c: V (G) → ℕ be a vertex coloring of G where adjacent vertices may be colored the same. For a vertex v of G, the neighborhood color set NC(v) is the set of colors of the neighbors of v. The coloring c is called a set coloring if NC(u) ≠ NC(v) for every pair u, v of adjacent vertices of G. The minimum number of colors required of such a coloring is called the set chromatic number x _s (G). A study is made of the set chromatic number of the join G+H of two graphs G and H. Sharp lower and upper bounds are established for x _s (G + H) in terms of x _s (G), x _s (H), and the clique numbers ω(G) and ω(H).     

On the adjacent vertex-distinguishing equitable edge coloring of graphs

Let G(V, E) be a graph. A k-adjacent vertex-distinguishing equatable edge coloring of G, k-AVEEC for short, is a proper edge coloring f if (1) C(u)≠C(v) for uv ∈ E(G), where C(u) = {f(uv)|uv ∈ E}, and (2) for any i, j = 1, 2,… k, we have ||Ei| |Ej|| ≤ 1, where Ei = {e|e ∈ E(G) and f(e) = i}. χáve (G) = min{k| there exists a k-AVEEC of G} is called the adjacent vertex-distinguishing equitable edge chromatic number of G. In this paper, we obtain the χáve (G) of some special graphs and present a conjecture.     

Triangle-free graphs whose independence number equals the degree

In a triangle-free graph, the neighbourhood of every vertex is an independent set. We investigate the class S of triangle-free graphs where the neighbourhoods of vertices are maximum independent sets. Such a graph G must be regular of degree d=α(G) and the fractional chromatic number must satisfy χ_f(G)=|G|/α(G). We indicate that S is a rich family of graphs by determining the rational numbers c for which there is a graph G∈S with χ_f(G)=c except for a small gap, where we cannot prove the full statement. The statements for c≥3 are obtained by using, modifying, and re-analysing constructions of Sidorenko, Mycielski, and Bauer, van den Heuvel and Schmeichel, while the case c<3 is settled by a recent result of Brandt and Thomassé. We will also investigate the relation between other parameters of certain graphs in S like chromatic number and toughness.     

On the topological lower bound for the multichromatic number

In 1976, Stahl [14] defined the m-tuple coloring of a graph G and formulated a conjecture on the multichromatic number of Kneser graphs. For m=1 this conjecture is Kneser’s conjecture, which was proved by Lovász in 1978 [10]. Here we show that Lovász’s topological lower bound given in this way cannot be used to prove Stahl’s conjecture. We obtain that the strongest index bound only gives the trivial m⋅ω(G) lower bound if m≥|V(G)|. On the other hand, the connectivity bound for Kneser graphs is constant if m is sufficiently large. These findings provide new examples of graphs showing that the gaps between the chromatic number, the index bound and the connectivity bound can be arbitrarily large.     

Strong edge colorings of uniform graphs

For a graph G=(V(G),E(G)), a strong edge coloring of G is an edge coloring in which every color class is an induced matching. The strong chromatic index of G, χ_s(G), is the smallest number of colors in a strong edge coloring of G. The strong chromatic index of the random graph G(n,p) was considered in Discrete Math. 281 (2004) 129, Austral. J. Combin. 10 (1994) 97, Austral. J. Combin. 18 (1998) 219 and Combin. Probab. Comput. 11 (1) (2002) 103. In this paper, we consider χ_s(G) for a related class of graphs G known as uniform or ε-regular graphs. In particular, we prove that for 0<ε?d<1, all (d,ε)-regular bipartite graphs G=(U∪V,E) with |U|=|V|?n₀(d,ε) satisfy χ_s(G)?ζ(ε)Δ(G)², where ζ(ε)→0 as ε→0 (this order of magnitude is easily seen to be best possible). Our main tool in proving this statement is a powerful packing result of Pippenger and Spencer (Combin. Theory Ser. A 51(1) (1989) 24).     

The forcing hull and forcing geodetic numbers of graphs

For every pair of vertices u,v in a graph, a u-v geodesic is a shortest path from u to v. For a graph G, let I_G[u,v] denote the set of all vertices lying on a u-v geodesic. Let S⊆V(G) and I_G[S] denote the union of all I_G[u,v] for all u,v∈S. A subset S⊆V(G) is a convex set of G if I_G[S]=S. A convex hull [S]_G of S is a minimum convex set containing S. A subset S of V(G) is a hull set of G if [S]_G=V(G). The hull number h(G) of a graph G is the minimum cardinality of a hull set in G. A subset S of V(G) is a geodetic set if I_G[S]=V(G). The geodetic number g(G) of a graph G is the minimum cardinality of a geodetic set in G. A subset F⊆V(G) is called a forcing hull (or geodetic) subset of G if there exists a unique minimum hull (or geodetic) set containing F. The cardinality of a minimum forcing hull subset in G is called the forcing hull number f_h(G) of G and the cardinality of a minimum forcing geodetic subset in G is called the forcing geodetic number f_g(G) of G. In the paper, we construct some 2-connected graph G with (f_h(G),f_g(G))=(0,0),(1,0), or (0,1), and prove that, for any nonnegative integers a, b, and c with a+b≥2, there exists a 2-connected graph G with (f_h(G),f_g(G),h(G),g(G))=(a,b,a+b+c,a+2b+c) or (a,2a+b,a+b+c,2a+2b+c). These results confirm a conjecture of Chartrand and Zhang proposed in [G. Chartrand, P. Zhang, The forcing hull number of a graph, J. Combin. Math. Combin. Comput. 36 (2001) 81-94].     

A connection between circular colorings and periodic schedules

We show that there is a curious connection between circular colorings of edge-weighted digraphs and periodic schedules of timed marked graphs. Circular coloring of an edge-weighted digraph was introduced by Mohar [B. Mohar, Circular colorings of edge-weighted graphs, J. Graph Theory 43 (2003) 107-116]. This kind of coloring is a very natural generalization of several well-known graph coloring problems including the usual circular coloring [X. Zhu, Circular chromatic number: A survey, Discrete Math. 229 (2001) 371-410] and the circular coloring of vertex-weighted graphs [W. Deuber, X. Zhu, Circular coloring of weighted graphs, J. Graph Theory 23 (1996) 365-376]. Timed marked graphs [R.M. Karp, R.E. Miller, Properties of a model for parallel computations: Determinancy, termination, queuing, SIAM J. Appl. Math. 14 (1966) 1390-1411] are used, in computer science, to model the data movement in parallel computations, where a vertex represents a task, an arc uv with weight c_uv represents a data channel with communication cost, and tokens on arc uv represent the input data of task vertex v. Dynamically, if vertex u operates at time t, then u removes one token from each of its in-arc; if uv is an out-arc of u, then at time t+c_uv vertex u places one token on arc uv. Computer scientists are interested in designing, for each vertex u, a sequence of time instants {f_u(1),f_u(2),f_u(3),…} such that vertex u starts its kth operation at time f_u(k) and each in-arc of u contains at least one token at that time. The set of functions is called a schedule of . Computer scientists are particularly interested in periodic schedules. Given a timed marked graph , they ask if there exist a period p>0 and real numbers x_u such that has a periodic schedule of the form f_u(k)=x_u+p(k−1) for each vertex u and any positive integer k. In this note we demonstrate an unexpected connection between circular colorings and periodic schedules. The aim of this note is to provide a possibility of translating problems and methods from one area of graph coloring to another area of computer science.     

Adjacent strong edge coloring of graphs

For a graph G(V, E), if a proper k-edge coloring ƒ is satisfied with C(u) ≠ C(v) for uv ∈ E(G), where $\text{C(u) = {ƒ(uv) | uv ∈ E}}$, then ƒ is called k-adjacent strong edge coloring of G, is abbreviated k-ASEC, and χ′_as(G) = min{k | k-ASEC of G} is called the adjacent strong edge chromatic number of G. In this paper, we discuss some properties of χ′_as(G), and obtain the χ′_as(G) of some special graphs and present a conjecture: if G are graphs whose order of each component is at least six, then χ′_as(G) ≤ Δ(G) + 2, where Δ(G) is the maximum degree of G.     

On distance two graphs of upper bound graphs

For a poset P=(X,≤), the upper bound graph (UB-graph) of P is the graph U=(X,E_U), where uv∈E_U if and only if u≠v and there exists m∈X such that u,v≤m. For a graph G, the distance two graph DS₂(G) is the graph with vertex set V(DS₂(G))=V(G) and u,v∈V(DS₂(G)) are adjacent if and only if d_G(u,v)=2. In this paper, we deal with distance two graphs of upper bound graphs. We obtain a characterization of distance two graphs of split upper bound graphs.     

On the packing chromatic number of Cartesian products, hexagonal lattice, and trees

The packing chromatic number χ_ρ(G) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into packings with pairwise different widths. Several lower and upper bounds are obtained for the packing chromatic number of Cartesian products of graphs. It is proved that the packing chromatic number of the infinite hexagonal lattice lies between 6 and 8. Optimal lower and upper bounds are proved for subdivision graphs. Trees are also considered and monotone colorings are introduced.     

Balanced decomposition of a vertex-colored graph

A balanced vertex-coloring of a graph G is a function c from V(G) to {−1,0,1} such that ∑{c(v):v∈V(G)}=0. A subset U of V(G) is called a balanced set if U induces a connected subgraph and ∑{c(v):v∈U}=0. A decomposition V(G)=V₁∪?∪V_r is called a balanced decomposition if V_i is a balanced set for 1≤i≤r.In this paper, the balanced decomposition number f(G) of G is introduced; f(G) is the smallest integer s such that for any balanced vertex-coloring c of G, there exists a balanced decomposition V(G)=V₁∪?∪V_r with |V_i|≤s for 1≤i≤r. Balanced decomposition numbers of some basic families of graphs such as complete graphs, trees, complete bipartite graphs, cycles, 2-connected graphs are studied.     

A sufficient condition for pancyclability of graphs

Let G be a graph of order n and S be a vertex set of q vertices. We call G,S-pancyclable, if for every integer i with 3≤i≤q there exists a cycle C in G such that |V(C)∩S|=i. For any two nonadjacent vertices u,v of S, we say that u,v are of distance two in S, denoted by d_S(u,v)=2, if there is a path P in G connecting u and v such that |V(P)∩S|≤3. In this paper, we will prove that if G is 2-connected and for all pairs of vertices u,v of S with d_S(u,v)=2, , then there is a cycle in G containing all the vertices of S. Furthermore, if for all pairs of vertices u,v of S with d_S(u,v)=2, , then G is S-pancyclable unless the subgraph induced by S is in a class of special graphs. This generalizes a result of Fan [G. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory B 37 (1984) 221-227] for the case when S=V(G).     

A new coloring theorem of Kneser graphs

In 1997, Johnson, Holroyd and Stahl conjectured that the circular chromatic number of the Kneser graphs KG(n,k) is equal to the chromatic number of these graphs. This was proved by Simonyi and Tardos (2006) [13] and independently by Meunier (2005) [10], if χ(KG(n,k)) is even. In this paper, we propose an alternative version of Kneser's coloring theorem to confirm the Johnson-Holroyd-Stahl conjecture.     

Independence and coloring properties of direct products of some vertex-transitive graphs

Let α(G) and χ(G) denote the independence number and chromatic number of a graph G, respectively. Let G×H be the direct product graph of graphs G and H. We show that if G and H are circular graphs, Kneser graphs, or powers of cycles, then α(G×H)=max{α(G)|V(H)|,α(H)|V(G)|} and χ(G×H)=min{χ(G),χ(H)}.