M(C_n)和M(W_n)图的邻点可区别的Ⅰ-全色数

研究了M(C_n)和M(W_n)图的邻点可区别的I-一全染色.根据M(C_n)和M(W_n)图的构造特征,利用构造函数法,构造了一个从点边集V(G)∪E(G)到色集合{1,2,…,k)的函数,给出了一种染色方案,得到了它们的邻点可区别的I-全色数.     

图M(P_m)和M(C_m)的点可区别边色数

本文研究了圈Cm和路Pm的Mycielski图的点可区别边染色问题.利用构造法给出了M(Cm)图的点可区别边染色法,得到了它的点可区别边色数,进而从图的结构关系,有效获得了M(Pm)图的相应点可区别边染色法和其边色数.该方法对研究存在结构关系的图染色问题具有重要的借鉴意义.     

图的一般邻点可区别均匀边染色和均匀全染色

提出了一般邻点可区别均匀边染色和全染色的新概念,研究了路P_n、圈C_n、星S_n、扇F_n、轮W_n、完全二部图K_(m,n)、2维平面网格图P_m×P_n的一般邻点可区别均匀边染色和全染色,具体给出这些图的一般邻点可区别均匀边染色和全染色指标.     

Pm□Pn的Smarandachely-邻点可区别边色数

图G的正常边染色f满足相邻点的色集合相不互包含时,该染色称为图G的Smarandcchely-邻点可区别边染色,其中S(x)={f(xw)|xw∈E(G)}称之为在f下的顶点x的色集合.该染色称为图G的Smarandchely-邻点可区别边染色.对图G进行的.Smarandchely-邻点可区别边染色所用最少颜色数称为图G的Smarandachely-邻点可区别边色数.讨论了Pm□Pn的Smarandchely-邻点可区别边色数.     

k-方图的邻点可区别无圈边染色

图G的一个正常边染色被称作邻点可区别无圈边染色,如果G中无二色圈,且相邻点关联边的色集合不同.图G的邻点可区别无圈边色数记为χ′_^(aa)(G),即图G的一个邻点可区别无圈边染色所用的最少颜色数.通过构造具体染色的方法,给出了一些k-方图的邻点可区别无圈边色数.     

三类平方图的点边邻点可区别全色数

根据平方图的结构性质,用穷染,递推的方法,讨论了路,圈,扇的平方图的点边邻点可区别全染色,得到了相应的色数,即并给出了一种染色方案.     

棋盘图的几种染色

染色问题是图论的重要研究内容之一,采用一种全新的方法给出了一类特殊图——棋盘图的邻点可区别边染色和邻点可区别全染色,并给出了相应的色数.     

关于图的一般邻点可区别全染色

提出了一般邻点可区别全染色的新概念,给出了路、圈、星、树、二部图、轮、扇、完全图的一般邻点可区别全染色指标.并据此提出猜想.     

关于广义θ-图的邻点可区别染色的简单证明

在《经济数学》等杂志上已经用穷染法给出了广义θ-图的邻点可区别全染色和邻点可区别边染色,但方法太过繁琐.本文结合P.N.Balister方法从结构上更为简洁的证明广义θ-图的邻点可区别染色的相关猜想.     

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

两个简单图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的邻点可区别的边色数与全色数.给出了两个简单图的半强积的邻点可区别染色数的一个上界,并证明了该上界是可达的.然后,讨论了两个树的不同半强积具有相同邻点可区别染色数的充分必要条件.另外,确定了一类图与完全图的半强积的邻点可区别染色数的精确值.     

Δ(G)=5的2-连通外平面图的邻点可区别全染色

Smarandachely邻点可区别全染色是指相邻点的色集合互不包含的邻点可区别全染色，是对邻点可区别全染色条件的进一步加强。本文研究了平面图的Smarandachely邻点可区别全染色，即根据2-连通外平面图的结构特点，利用分析法、数学归纳法，刻画了最大度为5的2-连通外平面图的Smarandachely邻点可区别全色数。证明了：如果$G$是一个$\Delta （G）=5$的2-连通外平面图，则$\chi_{\rm sat}（G）\leqslant 9$。     

图的Smarandachely邻点边色数的界

对图G的一个k-正常变染色法f,若图G中任意相邻两点的相邻边色集合互相不包含,那么称f为图G的一个k-Smarandachely邻点边染色(简记为k-SEC),而最小的正整数k称为图G的Smarandachely邻点边色数.尝试应用Lovasz局部引理来得到了Smarandachely邻点边色数的上界.     

图与其Mycielski图关联色数的关系

本文证明了对n阶图G,若其最大度△(G)的2倍不等于n,且G的关联色数等于△(G) 1,则M(G)的关联色数为△(M(G)) 1．同时还研究了树和完全二部图的Mycielski图的关联色数．文末提出了M(G)的关联色数猜想,其中M(G)为图G的Mycielski图．     

若干圈的广义冠图的2-强边染色

本文研究了圈的广义冠图CmFn,CmWn,CmCn的2-强边染色(D(2)-点可区别边染色).利用穷染、递推的方法得到了CmFn,CmWn,CmCn的2-强边色数(D(2)-点可区别边色数),并给出一种染色方案,推广了参考文献[6,7]的相应结果.     

平面图的强边染色

图$G$的强边染色是在正常边染色的基础上, 要求距离不超过$2$的任意两条边染不同的颜色, 强边染色所用颜色的最小整数称为图$G$的强边色数。本文首先给出极小反例的构型, 然后通过权转移法, 证明了$g(G)\geq5$, $\Delta(G)\geq6$且$5$-圈不相交的平面图的强边色数至多是$4\Delta(G)-1$。     

平面图的强边染色

图$G$的强边染色是在正常边染色的基础上, 要求距离不超过$2$的任意两条边染不同的颜色, 强边染色所用颜色的最小整数称为图$G$的强边色数。本文首先给出极小反例的构型, 然后通过权转移法, 证明了$g(G)\geq5$, $\Delta(G)\geq6$且$5$-圈不相交的平面图的强边色数至多是$4\Delta(G)-1$。     

List 2-facial 5-colorability of plane graphs with girth at least 12

A proper vertex coloring of a plane graph is 2-facial if any two different vertices joined by a facial walk of length 2 are colored differently, and it is 2-distance if every two vertices at distance 2 from each other are colored differently. Note that any 2-facial coloring of a subcubic graph is 2-distance.It is known that every plane graph with girth at least 14 has a 2-facial 5-coloring [M. Montassier, A. Raspaud, A note on 2-facial coloring of plane graphs. Inform. Process. Lett. 98 (6) (2006) 235–241], and that every planar subcubic graph with girth at least 13 has a list 2-distance 5-coloring [F. Havet, Choosability of square of planar subcubic graphs with large girth, Discrete Math. 309 (2009) 3353–3563].We strengthen these results by proving the list 2-facial 5-colorability of plane graphs with girth at least 12.     

图的邻点全和可区别全染色

设f:V(G)∪E(G)→{1,2,…,k}是图G的一个正常k-全染色。令■其中N(x)={y∈V(G)|xy∈E(G)}。对任意的边uv∈E(C),若有Φ(u)≠Φ(v)成立,则称f是图G的一个邻点全和可区别k-全染色。图G的邻点全和可区别全染色中最小的颜色数k叫做G的邻点全和可区别全色数,记为f tndi∑(G)。本文确定了路、圈、星、轮、完全二部图、完全图以及树的邻点全和可区别全色数,同时猜想:简单图G(≠K2)的邻点全和可区别全色数不超过△(G)+2。     

Colorings of plane graphs: A survey

After a brief historical account, a few simple structural theorems about plane graphs useful for coloring are stated, and two simple applications of discharging are given. Afterwards, the following types of proper colorings of plane graphs are discussed, both in their classical and choosability (list coloring) versions: simultaneous colorings of vertices, edges, and faces (in all possible combinations, including total coloring), edge-coloring, cyclic coloring (all vertices in any small face have different colors), 3-coloring, acyclic coloring (no 2-colored cycles), oriented coloring (homomorphism of directed graphs to small tournaments), a special case of circular coloring (the colors are points of a small cycle, and the colors of any two adjacent vertices must be nearly opposite on this cycle), 2-distance coloring (no 2-colored paths on three vertices), and star coloring (no 2-colored paths on four vertices). The only improper coloring discussed is injective coloring (any two vertices having a common neighbor should have distinct colors).