广义图K(n,m)的全色数

1965年,M.Behzad和Vizing分别提出了著名的全着色猜想:即对于简单图G有:XT(G)≤△+2,其中△是图G的最大度.本文确定了完全图Kn的广义图K(n,m)的全色数,并利用它证明了Lm×Kn(m≥3)是第Ⅰ型的.     

若干图的点强全染色(英文)

对图G及正整数k，映射f：满足：（1）任意e1，e3，如果e1，e2是相邻或相关联的，则有；（2）对u，v，w（G）有，则称f为G的一个k-点强全染色，并且K|G的社点强全染色称为G的点强全色数．本文讨论了一些特殊困的点强全色数，并提出了一个猜想：若G为每一分图的阶数不小于6的图，则（G），其中（G）为本文中定义的一新参数．     

路与完全图的笛卡尔积图和广义图K(n,m)的关联色数

Richrd A.Brualdi和J.Quinn Massey在[1]中引入了图的关联着色概念,并且提出了关联着色猜想,即每一个图G都可以用△(G)+2种色正常关联着色.B.Guiduli[2]说明关联着色的概念是I.Algor和N.Alon[3]提出的有向星荫度的一个特殊情况,并证实[1]的关联着色猜想是错的,给出图G的关联色数的一个新的上界是△(G)+O(Log(△G)).[4]确定了某些特殊图类的关联色数.本文给出了路和完全图的笛卡尔积图的关联色数,而且利用此结果又确定了完全图Kn的广义图K(n,m)的关联色数.     

广义Mycielski图的邻强边色数和邻点可区别全色数的两个上界

对简单图G,|V(G)|=p,n是自然数,Mn(G)被称为图G的广义Mycielski图,如果V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…;vn1,vn2,…,vnp},E(Mn(G))=E(G)∪{vijv(i+1)k|v0jv0k∈E(G),1≤j,k≤p,i=0,1,…,n-1}.文中针对简单图G与它的广义Mycielski图之间的关系,给出了G的广义Mycielski图的邻强边色数和邻点可区别全色数的两个上界.     

完全二部图广义Mycielski图的邻点可区别全色数与邻强边色数

得到了完全二部图Km,n的广义Mycielski图Ml(Km,n),当(l≥1,n≥m≥2)时的邻点可区别全色数与邻强边色数.     

若干图的点强全着色

图G(V,E)的一正常k-全着色σ称为G(V,E)的一个k-点强全着色,当且仅当v∈V(G),N[v]中的元素着不同颜色,其中N[v]={u|vu∈E(G)}∪{v}.并且vχsT(G)=min{k|存在G的一个k-点强全着色}称为G(V,E)的点强全色数.本文得到了一些特殊图的点强全色数χvTs(G),并提出猜想:对于简单图G,有k(G)≤χvTs(G)≤k(G)+1,这里k(G)表示图G中所有顶点间距离不超过2的点集的最大顶点数.     

一些图的Double图的点可区别全色数

文献【2】定义点可区别全染色,对—个图其所用最少染色数称为它的点可区别全色数．本文得到了星、扇和轮的Double图的点可区别全色数．     

广义(m,n)超环

本文研究了广义(m,n)超环,n元正则关系以及n元强正则关系等的一些性质.利用广义(m,n)超环间的同态关系以及正则和强正则关系,得到了(m,n)子超环和(m,n)超理想的不变性,广义(m,n)超环的商结构,以及构成商超环和商环的充分必要条件,推广了文献[5]的一些结果.     

路、圈的广义Mycielski图的邻点可区别Ⅰ-全色数

图G的邻点可区别Ⅰ-全染色是一个满足相邻顶点色集合不同的Ⅰ-全染色,其中任意一点的色集合包含该顶点及其关联边所染的颜色.所需颜色的最小数称为邻点可区别Ⅰ-全色数,记作χ_atⁱ(G).研究了路和圈的广义Mycielski图的邻点可区别Ⅰ-全色数:对于阶数n≥2的路P_n,当n=2,3,4时,有χ_atⁱ(M(P_n))=n+1;否则,χ_atⁱ(M(P_n))=n.对于阶数n≥3的圈C_n,当n=3,4时,有χ_atⁱ(M(C_n))=5;否则,χ_atⁱ(M(C_n))=n.     

若干Mycielski图的点可区别均匀全色数

研究了一些Mycielski图的点可区别均匀全染色(VDETC),利用构造法给出了路、圈、星和扇的Mycielski图的点可区别均匀全色数,验证了它们满足点可区别均匀全染色猜想(VDETCC).     

On the vertex face total chromatic number of planar graphs

Let G be a planar graph. The vertex face total chromatic number _χ13(G) of G is the least number of colors assigned to V(G)∪F(G) such that no adjacent or incident elements receive the same color. The main results of this paper are as follows: (1) We give the vertex face total chromatic number for all outerplanar graphs and modulus 3-regular maximal planar graphs. (2) We prove that if G is a maximal planar graph or a lower degree planar graph, i.e., ∠(G) ≤ 3, then _χ13(G) ≤ 6. © 1996 John Wiley & Sons, Inc.     

THE TOTAL CHROMATIC NUMBER OF PSEUDO-OUTERPLANAR GRAPHS

A Planar graph g is called a ipseudo outerplanar graph if there is a subset v.∈V(G),[V.]=i,such that G-V. is an outerplanar graph in particular when G-V.is a forest ,g is called a i-pseudo-tree .in this paper.the following results are proved;(1)the conjecture on the total coloring is true for all 1-pseudo-outerplanar graphs;(2)X1(G) 1 fo any 1-pseudo outerplanar graph g with △(G)≥3,where x4(G)is the total chromatic number of a graph g.     

The number of K m,m -free graphs

A graph is called H-free if it contains no copy of H. Denote by f _n (H) the number of (labeled) H-free graphs on n vertices. Erdős conjectured that f _n (H) ≤ 2^{(1+o(1))ex(n,H)}. This was first shown to be true for cliques; then, Erdős, Frankl, and R?dl proved it for all graphs H with χ(H)≥3. For most bipartite H, the question is still wide open, and even the correct order of magnitude of log₂ f _n (H) is not known. We prove that f _n (K _m,m ) ≤ 2 ^O (n ^2−1/m ) for every m, extending the result of Kleitman and Winston and answering a question of Erdős. This bound is asymptotically sharp for m∈{2,3}, and possibly for all other values of m, for which the order of ex(n,K _m,m ) is conjectured to be Θ(n ^2−1/m ). Our method also yields a bound on the number of K _m,m -free graphs with fixed order and size, extending the result of Füredi. Using this bound, we prove a relaxed version of a conjecture due to Haxell, Kohayakawa, and Łuczak and show that almost all K _3,3-free graphs of order n have more than 1/20·ex(n,K _3,3) edges.     

Game chromatic number of strong product graphs

The graph coloring game is a two-player game in which the two players properly color an uncolored vertex of G alternately. The first player wins the game if all vertices of G are colored, and the second wins otherwise. The game chromatic number of a graph G is the minimum integer k such that the first player has a winning strategy for the graph coloring game on G with k colors. There is a lot of literature on the game chromatic number of graph products, e.g., the Cartesian product and the lexicographic product. In this paper, we investigate the game chromatic number of the strong product of graphs, which is one of major graph products. In particular, we completely determine the game chromatic number of the strong product of a double star and a complete graph. Moreover, we estimate the game chromatic number of some King's graphs, which are the strong products of two paths.     

An improved upper bound on the adjacent vertex distinguishing total chromatic number of graphs

An adjacent vertex distinguishing total $k$-coloring of a graph $G$ is a proper total $k$-coloring of $G$ such that any pair of adjacent vertices have different sets of colors. The minimum number $k$ needed for such a total coloring of $G$ is denoted by ${\chi }_a^{\prime \prime }\left(G\right)$. In this paper we prove that ${\chi }_a^{\prime \prime }\left(G\right)\le 2\Delta \left(G\right)?1$ if $\Delta \left(G\right)\ge 4$, and ${\chi }_a^{\prime \prime }\left(G\right)\le ?\frac{5\Delta \left(G\right)+8}{3}?$ in general. This improves a result in Huang et al. (2012) which states that ${\chi }_a^{\prime \prime }\left(G\right)\le 2\Delta \left(G\right)$ for any graph with $\Delta \left(G\right)\ge 3$.     

The equitable total chromatic number of the graphHM(W n )

The equitable total chromatic number _Χet (G) of a graphG is the smallest integerk for whichG has a total k-coloring such that the number of vertices and edges in any two color classes differ by at most one. In this paper, we determine the equitable total chromatic number of one class of the graphs.