平面图的循环色数及临界性

循环着色是普通着色的推广．本文中,我们研究了一类平面图-“花图”的循环着色问题,证明了由2r 1个长为2n 1的圈构成的“辐路”长度为m的花图Fr,m,n的循环色数是2 1/(n-m/2),并证明了在这类图中去掉任何一个点或边后,循环色数都严格减少但普通色数不减少,即这类图是循环色临界的但不是普通色临界的．同时,我们还研究了循环着色与图Gkd中的链之间的关系,给出了两个等价的条件．     

图的星临界性

图的星着色是图的正常着色的推广。本文对图的星临界性及其与图的临界性之间的关系进行研究，给出了两类星临界但非临界的平面图。     

平面图的理论与四色问题(Ⅳ)——三着色与四色问题的几何表征

§16 三色问题 三色问题之有助于四色问题者乃是极大平面图的三色问题。因为实际上四色问题只需研究那些非3-可着色的极大平面图。可喜的是这点已得到完满解决。然,一般平面图的3-可着色的判定确非那样容易。本节着重于后者。 命题16.1 极大平面图3-可着色,当且仅当所有节点的次皆偶数。 证明 由推论8.2的对偶形式和推论8.1即得。 定理16.1 任何平面图4-可着色,当且仅当非Euler极大平面图4-可着色。 证明 由于一个图是Euler图,当且仅当其节点的次皆偶。必要性是直接的。充分     

平面图的理论与四色问题(V)——四色问题的计算机解决途径

§21可约性 这里只讨论4—可约性。首先,推广§7中的概念。一个构形R称为可约,如果任一平面图G,的4—着色均可由某小于G的平面图G′的4—着色导出。之谓G′小于G,记G′相似文献   

一类平面图的色多项式及其根的计算方法

图的色多项式P（G,x）是对图G用z（正整数）种颜色正常着色的数目。现在我们在实数或复数域上考虑图的色多项式P（G,x）,并且Beraha＆Kahane发现了具有复色根无限接近于4的平面图族。由此本文得到了一类平面图的色多项式和它的根．     

“另一个25阶最大平面图”G′_(M25)的四色着色

利用最大平面图着色的"简化降阶法",对一定拓扑结构的"另一个25阶最大平面图"G′_(M25)进行了着色运作.先逐点"降阶",再逐点"着色、升阶、着色",直至获得G′_(M25)的四色着色方案.由于着色过程中,有些点的着色是可以选择的,在这些点作任意选色后,只是找出其中的二个G′_(M25)的四色着色方案,即"四色着色方案壹"和"四色着色方案贰"(其他的四色着色方案未作求解).然后,在"四色着色方案壹"和"四色着色方案贰"的基础上,利用多层次的"二色交换法",相应地分别求出了G′_(M25)的二个相近四色着色方案集,即"相近四色着色方案集壹"和"相近四色着色方案集贰".在"相近四色着色方案集壹"中,含有72个不同的四色着色方案;在"相近四色着色方案集贰"中,含有156个不同的四色着色方案.文中对这二个相近四色着色方案集进行了分析,得到了有意义的结果.     

不含5-圈的平面图的无圈边着色

图G的一个无圈边着色是一个正常的边着色且不含双色的圈.图G的无圈边色数是图G的无圈边着色中所用色数的最小者.本文用反证法得到了不含5-圈的平面图G的无圈边色数的一个上界.     

不含K3的平面图最多是-4可着色的

提出了一种证明"四色猜想"的新思路.证明了"四色猜想"的一部分,即不含K3的平面图最多是-4可着色的,指出了另一部分的证明思路.     

最大平面图GM的孪生图GTM和对角线变换DT

提出了最大平面图GM的孪生图GTM和"孪生图对"的概念和定义,探讨了"孪生图对"的特性,分析了"孪生图对"的四色着色方案彼此间的关系,并由此形成了最大平面图着色的"对角线变换法".文中以二个实例("正二十面体的平面嵌入图";"Appel和Haken的例子")验证了研究的结果,同时也显示了孪生图GTM可被应用的场合及其实用性.     

最大平面图G_M的孪生图G_M~T和对角线变换DT

提出了最大平面图G_M的孪生图G_M~T和"孪生图对"的概念和定义,探讨了"孪生图对"的特性,分析了"孪生图对"的四色着色方案彼此间的关系,并由此形成了最大平面图着色的"对角线变换法".文中以二个实例("正二十面体的平面嵌入图";"Appel和Haken的例子")验证了研究的结果,同时也显示了孪生图G_M~T可被应用的场合及其实用性.     

List circular coloring of trees and cycles

Suppose G=(V, E) is a graph and p ≥ 2q are positive integers. A (p, q)‐coloring of G is a mapping ?: V → {0, 1, …, p‐1} such that for any edge xy of G, q ≤ |?(x)‐?(y)| ≤ p‐q. A color‐list is a mapping L: V → ({0, 1, …, p‐1}) which assigns to each vertex v a set L(v) of permissible colors. An L‐(p, q)‐coloring of G is a (p, q)‐coloring ? of G such that for each vertex v, ?(v) ∈ L(v). We say G is L‐(p, q)‐colorable if there exists an L‐(p, q)‐coloring of G. A color‐size‐list is a mapping ? which assigns to each vertex v a non‐negative integer ?(v). We say G is ?‐(p, q)‐colorable if for every color‐list L with |L(v)| = ?(v), G is L‐(p, q)‐colorable. In this article, we consider list circular coloring of trees and cycles. For any tree T and for any p ≥ 2q, we present a necessary and sufficient condition for T to be ?‐(p, q)‐colorable. For each cycle C and for each positive integer k, we present a condition on ? which is sufficient for C to be ?‐(2k+1, k)‐colorable, and the condition is sharp. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 249–265, 2007     

关于Mycielski图循环色数的猜想

通过引进Mycielski图点集的一类特殊划分,利用该划分在Mycielski图循环着色中的特点改进了如下猜想:完全图的Mycielski图的循环色数等于它的点色数.     

Mycielski图的循环色数

通过引入一类点集划分的概念,研究了Mylielski图循环染色的性质,证明了当完全图的点数足够大时,它的Mycielski图的循环色数与其点色数相等.     

The circular chromatic index of some class 2 graphs

In this paper we consider the circular edge coloring of four families of Class 2 graphs. For the first two we establish the exact value of the circular chromatic index. For the next two, namely Goldberg and Isaacs snarks we derive an upper bound on this graph invariant. Finally, we consider the computational complexity of some problems related to circular edge coloring.     

Claw‐free circular‐perfect graphs

The circular chromatic number of a graph is a well‐studied refinement of the chromatic number. Circular‐perfect graphs form a superclass of perfect graphs defined by means of this more general coloring concept. This article studies claw‐free circular‐perfect graphs. First, we prove that if G is a connected claw‐free circular‐perfect graph with χ(G)>ω(G), then min{α(G), ω(G)}=2. We use this result to design a polynomial time algorithm that computes the circular chromatic number of claw‐free circular‐perfect graphs. A consequence of the strong perfect graph theorem is that minimal imperfect graphs G have min{α(G), ω(G)}=2. In contrast to this result, it is shown in Z. Pan and X. Zhu [European J Combin 29(4) (2008), 1055–1063] that minimal circular‐imperfect graphs G can have arbitrarily large independence number and arbitrarily large clique number. In this article, we prove that claw‐free minimal circular‐imperfect graphs G have min{α(G), ω(G)}≤3. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 163–172, 2010     

Vertex-distinguishing E-total Coloring of Complete Bipartite Graph K_(7,n) when 7≤n≤95

Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints. For an E-total coloring f of a graph G and any vertex x of G, let C(x) denote the set of colors of vertex x and of the edges incident with x, we call C(x) the color set of x. If C(u)≠ C(v) for any two different vertices u and v of V(G), then we say that f is a vertex-distinguishing E-total coloring of G or a VDET coloring of G for short. The minimum number of colors required for a VDET coloring of G is denoted by χ_(vt)~e(G) and is called the VDET chromatic number of G. The VDET coloring of complete bipartite graph K_(7,n)(7 ≤ n ≤ 95) is discussed in this paper and the VDET chromatic number of K_(7,n)(7 ≤ n ≤ 95) has been obtained.     

The circular chromatic number of a digraph

We introduce the circular chromatic number χ_c of a digraph and establish various basic results. They show that the coloring theory for digraphs is similar to the coloring theory for undirected graphs when independent sets of vertices are replaced by acyclic sets. Since the directed k‐cycle has circular chromatic number k/(k – 1), for k ≥ 2, values of χ_c between 1 and 2 are possible. We show that in fact, χ_c takes on all rational values greater than 1. Furthermore, there exist digraphs of arbitrarily large digirth and circular chromatic number. It is NP‐complete to decide if a given digraph has χ_c at most 2. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 227–240, 2004     

Conflict-Free Coloring of Points and Simple Regions in the Plane

We study conflict-free colorings, where the underlying set systems arise in geometry. Our main result is a general framework for conflict-free coloring of regions with low union complexity. A coloring of regions is conflict-free if for any covered point in the plane, there exists a region that covers it with a unique color (i.e., no other region covering this point has the same color). For example, we show that we can conflict-free color any family of n pseudo-discs with O(log n) colors.