Note on cycle double covers of graphs

Kriesell [M. Kriesell, Contractions, cycle double covers and cyclic colorings in locally connected graphs, J. Combin. Theory Ser. B 96 (2006) 881-900] proved the cycle double cover conjecture for locally connected graphs. In this note, we give much shorter proofs for two stronger results.     

Random coloring evolution on graphs

In this short note we study how two colors, red and blue, painted on a given graph are evolved randomly according to a transition rule which aims to simulate how people influence each other. We shall also calculate the probability that the evolution will be trapped eventually using the martingale method.     

Indicated coloring of graphs

We study a graph coloring game in which two players collectively color the vertices of a graph in the following way. In each round the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent realization of this project. The smallest number of colors necessary for Ann to win the game on a graph $G$ (regardless of Ben’s strategy) is called the indicated chromatic number of $G$, and denoted by ${\chi }_i\left(G\right)$. We approach the question how much ${\chi }_i\left(G\right)$ differs from the usual chromatic number $\chi \left(G\right)$. In particular, whether there is a function $f$ such that ${\chi }_i\left(G\right)?f\left(\chi \left(G\right)\right)$ for every graph $G$. We prove that $f$ cannot be linear with leading coefficient less than $4/3$. On the other hand, we show that the indicated chromatic number of random graphs is bounded roughly by $4\chi \left(G\right)$. We also exhibit several classes of graphs for which ${\chi }_i\left(G\right)=\chi \left(G\right)$ and show that this equality for any class of perfect graphs implies Clique-Pair Conjecture for this class of graphs.     

Improper coloring of graphs on surfaces

A graph is -colorable if its vertex set can be partitioned into sets , such that for each , the subgraph of induced by has maximum degree at most . The Four Color Theorem states that every planar graph is -colorable, and a classical result of Cowen, Cowen, and Woodall shows that every planar graph is -colorable. In this paper, we extend both of these results to graphs on surfaces. Namely, we show that every graph embeddable on a surface of Euler genus is -colorable and -colorable. Moreover, these graphs are also -colorable and -colorable. We also prove that every triangle-free graph that is embeddable on a surface of Euler genus is -colorable. This is an extension of Grötzsch's Theorem, which states that triangle-free planar graphs are -colorable. Finally, we prove that every graph of girth at least 7 that is embeddable on a surface of Euler genus is -colorable. All these results are best possible in several ways as the girth condition is sharp, the constant maximum degrees cannot be improved, and the bounds on the maximum degrees depending on are tight up to a constant multiplicative factor.     

Legal coloring of graphs

The following computational problem was initiated by Manber and Tompa (22nd FOCS Conference, 1981): Given a graphG=(V, E) and a real functionf:V→R which is a proposed vertex coloring. Decide whetherf is a proper vertex coloring ofG. The elementary steps are taken to be linear comparisons. Lower bounds on the complexity of this problem are derived using the chromatic polynomial ofG. It is shown how geometric parameters of a space partition associated withG influence the complexity of this problem. Existing methods for analyzing such space partitions are suggested as a powerful tool for establishing lower bounds for a variety of computational problems.     

若干图的倍图的均匀邻强边染色

如果图G的一个正常边染色满足相邻点的色集不同,且任意两种颜色所染边数目相差不超过1,则称为均匀邻强边染色,其所用最少染色数称为均匀邻强边色数．本文得到了星、扇和轮的倍图的均匀邻强边色数．     

Randomly coloring random graphs

We consider the problem of generating a coloring of the random graph ??_n,p uniformly at random using a natural Markov chain algorithm: the Glauber dynamics. We assume that there are βΔ colors available, where Δ is the maximum degree of the graph, and we wish to determine the least β = β(p) such that the distribution is close to uniform in O(n log n) steps of the chain. This problem has been previously studied for ??_n,p in cases where np is relatively small. Here we consider the “dense” cases, where np ε [ω ln n, n] and ω = ω(n) → ∞. Our methods are closely tailored to the random graph setting, but we obtain considerably better bounds on β(p) than can be achieved using more general techniques. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

On coloring box graphs

We consider the chromatic number of a family of graphs we call box graphs, which arise from a box complex in n$n$-space. It is straightforward to show that any box graph in the plane has an admissible coloring with three colors, and that any box graph in n$n$-space has an admissible coloring with n+1$n+1$ colors. We show that for box graphs in n$n$-space, if the lengths of the boxes in the corresponding box complex take on no more than two values from the set {1,2,3}$\{1,2,3\}$, then the box graph is 3$3$-colorable, and for some graphs three colors are required. We also show that box graphs in 3-space which do not have cycles of length four (which we call “string complexes”) are 3$3$-colorable.     

Semistrong edge coloring of graphs

Weakening the notion of a strong (induced) matching of graphs, in this paper, we introduce the notion of a semistrong matching. A matching M of a graph G is called semistrong if each edge of M has a vertex, which is of degree one in the induced subgraph G[M]. We strengthen earlier results by showing that for the subset graphs and for the Kneser graphs the sizes of the maxima of the strong and semistrong matchings are equal and so are the strong and semistrong chromatic indices. Similar properties are conjectured for the n‐dimensional cube. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 39–47, 2005     

Star coloring of sparse graphs

A proper coloring of the vertices of a graph is called a star coloring if the union of every two color classes induces a star forest. The star chromatic number χ_s(G) is the smallest number of colors required to obtain a star coloring of G. In this paper, we study the relationship between the star chromatic number χ_s(G) and the maximum average degree Mad(G) of a graph G. We prove that:

• 1. If G is a graph with , then χ_s(G)≤4.
• 2. If G is a graph with and girth at least 6, then χ_s(G)≤5.
• 3. If G is a graph with and girth at least 6, then χ_s(G)≤6.

These results are obtained by proving that such graphs admit a particular decomposition into a forest and some independent sets. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 201–219, 2009     

Balanced coloring of bipartite graphs

Given a bipartite graph G(U∪V, E) with n vertices on each side, an independent set I∈G such that |U∩I|=|V∩I| is called a balanced bipartite independent set. A balanced coloring of G is a coloring of the vertices of G such that each color class induces a balanced bipartite independent set in G. If graph G has a balanced coloring we call it colorable. The coloring number χ_B(G) is the minimum number of colors in a balanced coloring of a colorable graph G. We shall give bounds on χ_B(G) in terms of the average degree $\bar{d}$ of G and in terms of the maximum degree Δ of G. In particular we prove the following:

• $\chi_{{{B}}}({{G}}) \leq {{max}} \{{{2}},\lfloor {{2}}\overline{{{d}}}\rfloor+{{1}}\}$.
• For any 0<ε<1 there is a constant Δ₀ such that the following holds. Let G be a balanced bipartite graph with maximum degree Δ≥Δ₀ and n≥(1+ε)2Δ vertices on each side, then $\chi_{{{B}}}({{G}})\leq \frac{{{{20}}}}{\epsilon^{{{2}}}} \frac{\Delta}{{{{ln}}}\,\Delta}$.

© 2009 Wiley Periodicals, Inc. J Graph Theory 64: 277–291, 2010     

Circular coloring of signed graphs

Let ( be two positive integers. We generalize the well‐studied notions of ‐colorings and of the circular chromatic number to signed graphs. This implies a new notion of colorings of signed graphs, and the corresponding chromatic number χ. Some basic facts on circular colorings of signed graphs and on the circular chromatic number are proved, and differences to the results on unsigned graphs are analyzed. In particular, we show that the difference between the circular chromatic number and the chromatic number of a signed graph is at most 1. Indeed, there are signed graphs where the difference is 1. On the other hand, for a signed graph on n vertices, if the difference is smaller than 1, then there exists , such that the difference is at most . We also show that the notion of ‐colorings is equivalent to r‐colorings (see [12] (X. Zhu, Recent developments in circular coloring of graphs, in Topics in Discrete Mathematics Algorithms and Combinatorics Volume 26 , Springer Berlin Heidelberg, 2006, pp. 497–550)).     

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.