n-Tuple colorings and associated graphs

The n-tuple graph coloring, which assigns to each vertex n colors, is defined together with its respective chromatic number x_n. It is proved that these numbers satisfy the inequality x_n ≥ 2 + x_n?1, and that equality holds only for bipartite graphs. Graphs $\text{G}{}_{\mathrm{n}}{}^{\mathrm{m}}$ are defined which play the same role for the n-tuple coloring that K_m plays for the conventional coloring. The chromatic numbers of various classes of graphs are also calculated.     

On total chromatic number of direct product graphs

Coloring of the graph products, especially vertex and edge coloring, has been widely researched for all types of graph products. For total graph coloring, as combination of edge and vertex coloring, Behzad and Vizing set Total Coloring Conjecture in mid 1960s. In this paper, we prove the conjecture for two specific direct graph products, for direct product of path and arbitrary graph G, P _n ×G, where χ′(G)=Δ(G), and expand the proof onto direct product of arbitrary cycle and a path P _n , C _m ×P _n . At the same time, the proofs provide the algorithms to color such graphs.     

On colored set partitions of type B n

Generalizing Reiner’s notion of set partitions of type B _n , we define colored B _n -partitions by coloring the elements in and not in the zero-block respectively. Considering the generating function of colored B _n -partitions, we get the exact formulas for the expectation and variance of the number of non-zero-blocks in a random colored B _n -partition. We find an asymptotic expression of the total number of colored B _n -partitions up to an error of O(n ^?1/2log^7/2 n], and prove that the centralized and normalized number of non-zero-blocks is asymptotic normal over colored B _n -partitions.     

<Emphasis Type="Italic">r</Emphasis>-Dynamic Chromatic Number of Some Line Graphs

An r-dynamic coloring of a graph G is a proper coloring c of the vertices such that |c(N(v))| ≥ min {r, deg(v)}, for each v ∈ V (G). The r-dynamic chromatic number of a graph G is the smallest k such that G admits an r-dynamic coloring with k colors. In this paper, we obtain the r-dynamic chromatic number of the line graph of helm graphs H_n for all r between minimum and maximum degree of H_n. Moreover, our proofs are constructive, what means that we give also polynomial time algorithms for the appropriate coloring. Finally, as the first, we define an equivalent model for edge coloring.     

Decompositions of pseudographs into closed trails of even sizes

We consider a graph L_n, with n even, which is a complete graph with an additional loop at each vertex and minus a 1-factor and we prove that it is edge-disjointly decomposable into closed trails of even lengths greater than four, whenever these lengths sum up to the size of the graph L_n. We also show that this statement remains true if we remove from L_n two loops attached to nonadjacent vertices. Consequently, we improve P. Wittmann’s result on the upper bound of the irregular coloring number c(G) of a 2-regular graph G of size n, by determining that this number is, with a discrepancy of at most one, equal to if all components of G have even orders.     

On the densities of cliques and independent sets in graphs

Let r; s≥2 be integers. Suppose that the number of blue r-cliques in a red/blue coloring of the edges of the complete graph K _n is known and fixed. What is the largest possible number of red s-cliques under this assumption? The well known Kruskal-Katona theorem answers this question for r = 2 or s = 2. Using the shifting technique from extremal set theory together with some analytical arguments, we resolve this problem in general and prove that in the extremal coloring either the blue edges or the red edges form a clique.     

A note on acyclic edge coloring of complete bipartite graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic (2-colored) cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a^′(G). Let Δ=Δ(G) denote the maximum degree of a vertex in a graph G. A complete bipartite graph with n vertices on each side is denoted by K_n,n. Alon, McDiarmid and Reed observed that a^′(K_p−1,p−1)=p for every prime p. In this paper we prove that a^′(K_p,p)≤p+2=Δ+2 when p is prime. Basavaraju, Chandran and Kummini proved that a^′(K_n,n)≥n+2=Δ+2 when n is odd, which combined with our result implies that a^′(K_p,p)=p+2=Δ+2 when p is an odd prime. Moreover we show that if we remove any edge from K_p,p, the resulting graph is acyclically Δ+1=p+1-edge-colorable.     

Incidence coloring of the squares of some graphs

The incidence chromatic number of G, denoted by χ_i(G), is the least number of colors such that G has an incidence coloring. In this paper, we determine the incidence chromatic number of the powers of paths, trees, which are min{n,2k+1}, and Δ(T²)+1, respectively. For the square of a Halin graph, we give an upper bound of its incidence chromatic number.     

Mono-multi bipartite Ramsey numbers, designs, and matrices

Eroh and Oellermann defined BRR(G₁,G₂) as the smallest N such that any edge coloring of the complete bipartite graph K_N,N contains either a monochromatic G₁ or a multicolored G₂. We restate the problem of determining BRR(K_1,λ,K_r,s) in matrix form and prove estimates and exact values for several choices of the parameters. Our general bound uses Füredi's result on fractional matchings of uniform hypergraphs and we show that it is sharp if certain block designs exist. We obtain two sharp results for the case r=s=2: we prove BRR(K_1,λ,K_2,2)=3λ-2 and that the smallest n for which any edge coloring of K_λ,n contains either a monochromatic K_1,λ or a multicolored K_2,2 is λ².     

A note on coloring sparse random graphs

Coja-Oghlan and Taraz [Amin Coja-Oghlan, Anusch Taraz, Exact and approximative algorithms for coloring , Random Structures and Algorithms 24 (3) (2004) 259-278] presented a graph coloring algorithm that has expected linear running time for random graphs with edge probability p satisfying np≤1.01. In this work, we develop their analysis by exploiting generating function techniques. We show that, in fact, their algorithm colors G_n,p with the minimal number of colors and has expected linear running time, provided that np≤1.33.     

On Ramsey numbers for circuits

Denote by r_k(n) the largest integer for which there exists some way of coloring the edges of a complete graph on r_k(n) vertices in k colors without forcing the appearance of a monochromatic simple circuit of length n. A new lower bound for r_k(5) is obtained.     

Neighbor Sum Distinguishing Index

We consider proper edge colorings of a graph G using colors of the set {1, . . . , k}. Such a coloring is called neighbor sum distinguishing if for any pair of adjacent vertices x and y the sum of colors taken on the edges incident to x is different from the sum of colors taken on the edges incident to y. The smallest value of k in such a coloring of G is denoted by ndi_Σ(G). In the paper we conjecture that for any connected graph G ≠ C ₅ of order n ≥ 3 we have ndi_Σ(G) ≤ Δ(G) + 2. We prove this conjecture for several classes of graphs. We also show that ndi_Σ(G) ≤ 7Δ(G)/2 for any graph G with Δ(G) ≥ 2 and ndi_Σ(G) ≤ 8 if G is cubic.     

r-tuple colorings of uniquely colorable graphs

An r-tuple coloring of a graph is one in which r colors are assigned to each point of the graph so that the sets of colors assigned to adjacent points are always disjoint. We investigate the question of whether a uniquely n-colorable graph can receive an r-tuple coloring with fewer than nr colors. We show that this cannot happen for n=3 and r=2 and that for a given n and r to establish the conjecture that no uniquely n-colorable graph can receive an r-tuple coloring from fewer than nr colors it suffices to prove it for on a finite set of uniquely n-colorable graphs.     

Vertex Distinguishing Equitable Total Chromatic Number of Join Graph

A vertex distinguishing equitable total coloring of graph G is a proper total coloring of graph G such that any two distinct vertices＇ coloring sets are not identical and the difference of the elements colored by any two colors is not more than 1. In this paper we shall give vertex distinguishing equitable total chromatic number of join graphs Pn VPn, Cn VCn and prove that they satisfy conjecture 3, namely, the chromatic numbers of vertex distinguishing total and vertex distinguishing equitable total are the same for join graphs Pn V Pn and Cn ∨ Cn.     

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.     

Coloring graphs from random lists of size 2

Let G=G(n) be a graph on n vertices with girth at least g and maximum degree bounded by some absolute constant Δ. Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all 2-subsets of a color set C of size σ(n). In this paper we determine, for each fixed g and growing n, the asymptotic probability of the existence of a proper coloring φ such that φ(v)∈L(v) for all v∈V(G). In particular, we show that if g is odd and σ(n)=ω(n^1/(2g−2)), then the probability that G has a proper coloring from such a random list assignment tends to 1 as n→∞. Furthermore, we show that this is best possible in the sense that for each fixed odd g and each n≥g, there is a graph H=H(n,g) with bounded maximum degree and girth g, such that if σ(n)=o(n^1/(2g−2)), then the probability that H has a proper coloring from such a random list assignment tends to 0 as n→∞. A corresponding result for graphs with bounded maximum degree and even girth is also given. Finally, by contrast, we show that for a complete graph on n vertices, the property of being colorable from random lists of size 2, where the lists are chosen uniformly at random from a color set of size σ(n), exhibits a sharp threshold at σ(n)=2n.     

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

A note on short cycles in a hypercube

How many edges can a quadrilateral-free subgraph of a hypercube have? This question was raised by Paul Erd?s about 27 years ago. His conjecture that such a subgraph asymptotically has at most half the edges of a hypercube is still unresolved. Let f(n,C_l) be the largest number of edges in a subgraph of a hypercube Q_n containing no cycle of length l. It is known that f(n,C_l)=o(|E(Q_n)|), when l=4k, k?2 and that . It is an open question to determine f(n,C_l) for l=4k+2, k?2. Here, we give a general upper bound for f(n,C_l) when l=4k+2 and provide a coloring of E(Q_n) by four colors containing no induced monochromatic C₁₀.     

Local coloring of Kneser graphs

A local coloring of a graph G is a function c:V(G)→N having the property that for each set S⊆V(G) with 2≤|S|≤3, there exist vertices u,v∈S such that |c(u)−c(v)|≥m_S, where m_S is the number of edges of the induced subgraph 〈S〉. The maximum color assigned by a local coloring c to a vertex of G is called the value of c and is denoted by χ_?(c). The local chromatic number of G is χ_?(G)=min{χ_?(c)}, where the minimum is taken over all local colorings c of G. The local coloring of graphs was introduced by Chartrand et al. [G. Chartrand, E. Salehi, P. Zhang, On local colorings of graphs, Congressus Numerantium 163 (2003) 207-221]. In this paper the local coloring of Kneser graphs is studied and the local chromatic number of the Kneser graph K(n,k) for some values of n and k is determined.     

Worst case analysis of a graph coloring algorithm

In this paper, we show that a graph coloring heuristic developed by Brélaz may use n colors to color a 3-colorable graph with O(n) vertices.