图的半强积的邻点可区别染色

两个简单图G与H的半强积G·H是具有顶点集V(G)×V(H)的简单图,其中两个顶点(u,v)与(u',v')相邻当且仅当u=u'且vv'∈E(H),或uu'∈E(G)且vv'∈E(H).图的邻点可区别边(全)染色是指相邻点具有不同色集的正常边(全)染色.统称图的邻点可区别边染色与邻点可区别全染色为图的邻点可区别染色.图G的邻点可区别染色所需的最少的颜色数称为邻点可区别染色数,并记为X_a~((r))(G),其中r=1,2,且X_a~((1))(G)与X_a~((2))(G)分别表示G的邻点可区别的边色数与全色数.给出了两个简单图的半强积的邻点可区别染色数的一个上界,并证明了该上界是可达的.然后,讨论了两个树的不同半强积具有相同邻点可区别染色数的充分必要条件.另外,确定了一类图与完全图的半强积的邻点可区别染色数的精确值.     

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.     

Acyclic edge colorings of graphs

A proper coloring of the edges of a graph G is called acyclic if there is no 2‐colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. For certain graphs G, a′(G) ≥ Δ(G) + 2 where Δ(G) is the maximum degree in G. It is known that a′(G) ≤ 16 Δ(G) for any graph G. We prove that there exists a constant c such that a′(G) ≤ Δ(G) + 2 for any graph G whose girth is at least cΔ(G) log Δ(G), and conjecture that this upper bound for a′(G) holds for all graphs G. We also show that a′(G) ≤ Δ + 2 for almost all Δ‐regular graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 157–167, 2001     

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

Adjacent strong edge colorings and total colorings of regular graphs

It is conjectured that χas(G) = χt(G) for every k-regular graph G with no C5 component (k 2). This conjecture is shown to be true for many classes of graphs, including: graphs of type 1; 2-regular, 3-regular and (|V (G)| - 2)-regular graphs; bipartite graphs; balanced complete multipartite graphs; k-cubes; and joins of two matchings or cycles.     

Acyclic edge colorings of planar graphs and seriesparallel graphs

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ⩽ Δ(G) + 2 for any graphs. For planar graphs G with girth g(G), we prove that a′(G) ⩽ max{2Δ(G) − 2, Δ(G) + 22} if g(G) ⩾ 3, a′(G) ⩽ Δ(G) + 2 if g(G) ⩾ 5, a′(G) ⩽ Δ(G) + 1 if g(G) ⩾ 7, and a′(G) = Δ(G) if g(G) ⩾ 16 and Δ(G) ⩾ 3. For series-parallel graphs G, we have a′(G) ⩽ Δ(G) + 1. This work was supported by National Natural Science Foundation of China (Grant No. 10871119) and Natural Science Foundation of Shandong Province (Grant No. Y2008A20).     

r-Strong edge colorings of graphs

Let G be a graph and for any natural number r, denotes the minimum number of colors required for a proper edge coloring of G in which no two vertices with distance at most r are incident to edges colored with the same set of colors. In [Z. Zhang, L. Liu, J. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett. 15 (2002) 623-626] it has been proved that for any tree T with at least three vertices, . Here we generalize this result and show that . Moreover, we show that if for any two vertices u and v with maximum degree d(u,v)?3, then . Also for any tree T with Δ(T)?3 we prove that . Finally, it is shown that for any graph G with no isolated edges, .     

On edge colorings of 1-toroidal graphs

A graph is 1-toroidal, if it can be embedded in the torus so that each edge is crossed by at most one other edge. In this paper, it is proved that every 1-toroidal graph with maximum degree Δ≥ 10 is of class one in terms of edge coloring. Meanwhile, we show that there exist class two 1-toroidal graphs with maximum degree Δ for each Δ≤ 8.     

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.     

Vertex‐distinguishing edge colorings of graphs

We consider lower bounds on the the vertex‐distinguishing edge chromatic number of graphs and prove that these are compatible with a conjecture of Burris and Schelp 8 . We also find upper bounds on this number for certain regular graphs G of low degree and hence verify the conjecture for a reasonably large class of such graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 95–109, 2003     

On the adjacent vertex-distinguishing acyclic edge coloring of some graphs

A proper edge coloring of a graph G is called adjacent vertex-distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the coloring set of edges incident with u is not equal to the coloring set of edges incident with v, where uv ∈ E(G). The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by x′ _Aa (G), is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. If a graph G has an adjacent vertex distinguishing acyclic edge coloring, then G is called adjacent vertex distinguishing acyclic. In this paper, we obtain adjacent vertex-distinguishing acyclic edge coloring of some graphs and put forward some conjectures.     

Some results on cyclic interval edge colorings of graphs

A proper edge coloring of a graph G with colors is called a cyclic interval t‐coloring if for each vertex v of G the edges incident to v are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. We prove that a bipartite graph G of even maximum degree admits a cyclic interval ‐coloring if for every vertex v the degree satisfies either or . We also prove that every Eulerian bipartite graph G with maximum degree at most eight has a cyclic interval coloring. Some results are obtained for ‐biregular graphs, that is, bipartite graphs with the vertices in one part all having degree a and the vertices in the other part all having degree b; it has been conjectured that all these have cyclic interval colorings. We show that all (4, 7)‐biregular graphs as well as all ‐biregular () graphs have cyclic interval colorings. Finally, we prove that all complete multipartite graphs admit cyclic interval colorings; this proves a conjecture of Petrosyan and Mkhitaryan.     

Vertex‐distinguishing edge colorings of random graphs

A proper edge coloring of a simple graph G is called vertex‐distinguishing if no two distinct vertices are incident to the same set of colors. We prove that the minimum number of colors required for a vertex‐distinguishing coloring of a random graph of order n is almost always equal to the maximum degree Δ(G) of the graph. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 89–97, 2002     

A note on transformations of edge colorings of bipartite graphs

The author and A. Mirumian proved the following theorem: Let G be a bipartite graph with maximum degree Δ and let t,n be integers, tnΔ. Then it is possible to obtain, from one proper edge t-coloring of G, any proper edge n-coloring of G using only transformations of 2-colored and 3-colored subgraphs such that the intermediate colorings are also proper. In this note we show that if t>Δ then we can transform f to g using only transformations of 2-colored subgraphs. We also correct the algorithm suggested in [A.S. Asratian, Short solution of Kotzig's problem for bipartite graphs, J. Combin. Theory Ser. B 74 (1998) 160–168] for transformation of f to g in the case when t=n=Δ and G is regular.     

Almost regular edge colorings and regular decompositions of complete graphs

For k = 1 and k = 2, we prove that the obvious necessary numerical conditions for packing t pairwise edge‐disjoint k‐regular subgraphs of specified orders m₁,m₂,… ,m_t in the complete graph of order n are also sufficient. To do so, we present an edge‐coloring technique which also yields new proofs of various known results on graph factorizations. For example, a new construction for Hamilton cycle decompositions of complete graphs is given. © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 499–506, 2008     

A note on one-sided interval edge colorings of bipartite graphs

For a bipartite graph G with parts X and Y, an X-interval coloring is a proper edge coloring of G by integers such that the colors on the edges incident to any vertex in X form an interval. Denote by ${\chi }_{int}^{\prime }(G,X)$ the minimum k such that G has an X-interval coloring with k colors. Casselgren and Toft (2016) [12] asked whether there is a polynomial $P(\mathrm{\Delta })$ such that if G has maximum degree at most Δ, then ${\chi }_{int}^{\prime }(G,X)\le P(\mathrm{\Delta })$. In this short note, we answer this question in the affirmative; in fact, we prove that a cubic polynomial suffices. We also deduce some improved upper bounds on ${\chi }_{int}^{\prime }(G,X)$ for bipartite graphs with small maximum degree.     

Concise proofs for adjacent vertex-distinguishing total colorings

Let G=(V,E) be a graph and f:(V∪E)→[k] be a proper total k-coloring of G. We say that f is an adjacent vertex- distinguishing total coloring if for any two adjacent vertices, the set of colors appearing on the vertex and incident edges are different. We call the smallest k for which such a coloring of G exists the adjacent vertex-distinguishing total chromatic number, and denote it by χ_at(G). Here we provide short proofs for an upper bound on the adjacent vertex-distinguishing total chromatic number of graphs of maximum degree three, and the exact values of χ_at(G) when G is a complete graph or a cycle.