Feasible Graphs and Colorings

The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there is an effective degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring.     

Edge Colorings of Embedded Graphs

 In his paper, we discuss under what conditions graphs embedded in a surface Σ will be class one. Received: August 14, 1997 Revised: April 15, 1998     

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

Polychromatic Colorings of Plane Graphs

We show that the vertices of any plane graph in which every face is incident to at least g vertices can be colored by ⌊(3g−5)/4⌋ colors so that every color appears in every face. This is nearly tight, as there are plane graphs where all faces are incident to at least g vertices and that admit no vertex coloring of this type with more than ⌊(3g+1)/4⌋ colors. We further show that the problem of determining whether a plane graph admits a vertex coloring by k colors in which all colors appear in every face is in ℘ for k=2 and is -complete for k=3,4. We refine this result for polychromatic 3-colorings restricted to 2-connected graphs which have face sizes from a prescribed (possibly infinite) set of integers. Thereby we find an almost complete characterization of these sets of integers (face sizes) for which the corresponding decision problem is in ℘, and for the others it is -complete. Research of N. Alon was supported in part by the Israel Science Foundation, by a USA–Israeli BSF grant, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. Research of R. Berke was supported in part by JSPS Global COE program “Computationism as a Foundation for the Sciences.” Research of K. Buchin and M. Buchin was supported by the Netherlands’ Organisation for Scientific Research (NWO) under BRICKS/FOCUS project no. 642.065.503. Research of P. Csorba was supported by DIAMANT, an NWO mathematics cluster. Research of B. Speckmann was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.022.707.     

Achromatic and Harmonious Colorings of Circulant Graphs

A proper vertex coloring of a graph G is achromatic (respectively harmonious) if every two colors appear together on at least one (resp. at most one) edge. The largest (resp. the smallest) number of colors in an achromatic (resp. a harmonious) coloring of G is called the achromatic (resp. harmonious chromatic) number of G and denoted by (resp. ). For a finite set of positive integers and a positive integer n, a circulant graph, denoted by , is an undirected graph on the set of vertices that has an edge if and only if either or is a member of (where substraction is computed modulo n). For any fixed set , we show that is asymptotically equal to , with the error term . We also prove that is asymptotically equal to , with the error term . As corollaries, we get results that improve, for a fixed k, the previously best estimations on the lengths of a shortest k‐radius sequence over an n‐ary alphabet (i.e., a sequence in which any two distinct elements of the alphabet occur within distance k of each other) and a longest packing k‐radius sequence over an n‐ary alphabet (which is a dual counterpart of a k‐radius sequence).     

一些图的邻点可区别关联着色

在图的关联着色概念的基础上定义了图的邻点可区别关联着色及邻点可区别关联色数,研究了圈、完全二部图、Cm.Fn图的邻点可区别关联着色,并确定了它们的邻点可区别关联色数.     

圈和完全图的点可区别VE-全染色(英文)

Let G be a simple graph of order at least 2.A VE-total-coloring using k colors of a graph G is a mapping f from V (G) E(G) into {1,2,···,k} such that no edge receives the same color as one of its endpoints.Let C(u)={f(u)} {f(uv) | uv ∈ E(G)} be the color-set of u.If C(u)=C(v) for any two vertices u and v of V (G),then f is called a k-vertex-distinguishing VE-total coloring of G or a k-VDVET coloring of G for short.The minimum number of colors required for a VDVET coloring of G is denoted by χ ve vt (G) and it is called the VDVET chromatic number of G.In this paper we get cycle C n,path P n and complete graph K n of their VDVET chromatic numbers and propose a related conjecture.     

Dominator Colorings in Some Classes of Graphs

A dominator coloring is a coloring of the vertices of a graph such that every vertex is either alone in its color class or adjacent to all vertices of at least one other class. We present new bounds on the dominator coloring number of a graph, with applications to chordal graphs. We show how to compute the dominator coloring number in polynomial time for P ₄-free graphs, and we give a polynomial-time characterization of graphs with dominator coloring number at most 3.     

Total Colorings of Planar Graphs without Small Cycles

Let G be a planar graph with maximum degree Δ. It is proved that if Δ ≥ 8 and G is free of k-cycles for some k ∈ {5,6}, then the total chromatic number χ′′(G) of G is Δ + 1. This work is supported by a research grant NSFC(60673047) and SRFDP(20040422004) of China. Received: February 27, 2007. Final version received: December 12, 2007.     

Total Colorings of Graphs with Minimum Sum of Colors

The total chromatic sum of a graph is the minimum sum of colors (natural numbers) taken over all proper colorings of vertices and edges of a graph. We construct infinite families of graphs for which the minimum number of colors to achieve the total chromatic sum is larger than the total chromatic number.     

Vertex-Distinguishing Edge Colorings of Graphs with Degree Sum Conditions

An edge coloring is called vertex-distinguishing if every two distinct vertices are incident to different sets of colored edges. The minimum number of colors required for a vertex-distinguishing proper edge coloring of a simple graph G is denoted by c￠_vd(G){\chi'_{vd}(G)}. It is proved that c￠_vd(G) ￡ D(G)+5{\chi'_{vd}(G)\leq\Delta(G)+5} if G is a connected graph of order n ≥ 3 and s₂(G) 3 \frac2n3{\sigma_{2}(G)\geq\frac{2n}{3}}, where σ ₂(G) denotes the minimum degree sum of two nonadjacent vertices in G.     

叉连图的邻点可区别全染色

邻点可区别全染色猜想得到了国内外许多学者的关注和研究.迄今为止,这个猜想没有得到证明,也没有关于这个猜想的反例.叉连图对邻点可区别全染色猜想成立给予了证明,并给出了精确值.同时,证明了:存在无穷多个图,它们中的每一个图H至少包含一个真子图HH~1,使得x_as~″(H~1)x_as~″(H).     

图在三种约束条件下的正常全染色

设f:V(G)∪E(G)→{1,2,…,k}是简单图G的一个正常k-全染色.令C(f,u)={f(e):e∈N_e(u)},C[f,u]=C(f,u)∪{f(u)},C_2[f,u]=C(f,u)∪{f(x):x∈N(u)}∪{f(u)}.N(u)表示顶点u的邻集,N_e(u)表示与顶点u的相关联的边的集合.令C[f;x]={C(f,x);C[f,x];C_2[f,x]},对任意的xy∈E(G),G[f;x]≠C[f;y]表示C(f,x)≠C(f,y),C[f,x]≠C[f,y],C_2[f,x]≠C_3[f,y]同时成立.对任意的边xy∈E(G),如果有C[f;x]≠C[f;y]成立,则称f是图G的一个k-(3)-邻点可区别全染色(简记为(3)-AVDTC).图G的(3)-邻点可区别全染色中最小的颜色数叫做G的(3)-邻点可区别全色数,记为x_((3)as)″(G).研究了联图,完全二部图的(3)-邻点可区别全染色,得到了它们的(3)-邻点可区别全色数.     

路和圈上的卡氏乘积图的关联着色数(英文)

本文给出了路与路,路与圈的卡氏乘积图的关联着色数的完整刻画.对于圈与圈的卡氏乘积图的情形,也给出了其关联着色数的上界为乘积图的最大度加三,并且又给出了几类其关联着色数小于其最大度加三的圈与圈的卡氏乘积图类.     

Cyclic 4‐Colorings of Graphs on Surfaces

To attack the Four Color Problem, in 1880, Tait gave a necessary and sufficient condition for plane triangulations to have a proper 4‐vertex‐coloring: a plane triangulation G has a proper 4‐vertex‐coloring if and only if the dual of G has a proper 3‐edge‐coloring. A cyclic coloring of a map G on a surface F² is a vertex‐coloring of G such that any two vertices x and y receive different colors if x and y are incident with a common face of G. In this article, we extend the result by Tait to two directions, that is, considering maps on a nonspherical surface and cyclic 4‐colorings.     

可变抽样区间的累积合格品数控制图

本文提出了可变抽样区间的累积合格品数控制图.计算了它的发信号前平均时间,并同固定抽样区间的累积合格品数控制图进行了效率比较.     

不含5-圈和相邻6-圈的平面图的全染色

图的正常k-全染色是用k种颜色给图的顶点和边同时进行染色,使得相邻或者相关联的元素(顶点或边)染不同的染色.使得图G存在正常k-全染色的最小正整数k,称为图G的全色数,用χ″(G)表示.证明了若图G是最大度△≥6且不含5-圈和相邻6-圈的平面图,则χ″(G)=△+1.