一些联图的均匀全染色

对一个正常的全染色满足各种颜色所染元素数(点或边)相差不超过1时,称为均匀全染色,其所用最少染色数称为均匀全色数.本文证明了图在若干情况下的均匀全色数定理,得到C_m∨S_nC_m∨ F_n和C∨W_n的均匀全色数.     

若干倍图的均匀全染色(英文)

如果图G的一个正常全染色满足任意两种颜色所染元素(点或边)数目相差不超过1,则称为G的均匀全染色,其所用最少染色数称为均匀全色数.本文得到了星、扇和轮的倍图的均匀全色数.     

关于一类二部图的均匀邻点可区别全染色

若图的邻点可区别全染色的各色所染元素数之差不超过1,则称该染色法为图的均匀邻点可区别全染色,而所用的最少颜色数称为该图的均匀邻点可区别全色数.本文给出了一类二部图的均匀邻点可区别全染色数.     

若干Mycielski图的均匀染色

如果图G的一个正常顶点染色满足任两个色类中的顶点数相差不超过1,则称为G的均匀染色.研究了一些Mycielski图的均匀染色,给出了路、圈、完全图和广义星图的Mycielski图的均匀色数.     

Equitable Coloring of Complete r-partite Graphs

A graph is equitably k-colorable if its vertices can be partitioned into k independent sets of as near equal sizes as possible. In this paper, we determine a sufficient and necessary condition for which a complete r-partite graph is equitably k-colorable. From this result, we can provide another way to prove some previous results.     

最大度为8不含特定子图的平面图的全染色

全染色是对图G的顶点和边同时进行正常染色,至少要用Δ+1个色才能对图G进行正常全染色.本文运用权转移的方法,证明了最大度为8的不含特定子图的简单平面图是9-全可染的.     

P_n~k的均匀全染色

设G(V,E)是一个简单图,f是G的一个k-正常全染色,若f满足||Vi∪Ei|-|Vj∪Ej||≤1(i≠j),其中Vi∪Ei={v|f(v)=i}∪{e|f(e)=i},则称f为G的k-均匀全染色,简记为k-ETC.并称eχT(G)=min{k|G存在k-均匀全染色}为G的均匀全染色数.本文将通过很好的全染色方法得到eχT(Pkn)=5(n≥2k+1),并证明了对Pkn,[5]中猜想是正确的.     

Equitable Coloring of Three Classes of 1-planar Graphs

A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A plane graph with near-independent crossings or independent crossings, say NIC-planar graph or IC-planar graph, is a 1-planar graph with the restriction that for any two crossings the four crossed edges are incident with at most one common vertex or no common vertices, respectively. In this paper, we prove that each 1-planar graph, NIC-planar graph or IC-planar graph with maximum degree Δ at least 15, 13 or 12 has an equitable Δ-coloring, respectively. This verifies the well-known Chen-Lih-Wu Conjecture for three classes of 1-planar graphs and improves some known results.     

Induced-Universal Graphs for Graphs with Bounded Maximum Degree

For a family \(\mathcal {F}\) of graphs, a graph U is induced-universal for \({\mathcal{F}}\) if every graph in \({\mathcal{F}}\) is an induced subgraph of U. We give a construction for an induced-universal graph for the family of graphs on n vertices with degree at most r, which has \(Cn^{\lfloor (r+1)/2\rfloor}\) vertices and \(Dn^{2\lfloor (r+1)/2\rfloor -1}\) edges, where C and D are constants depending only on r. This construction is nearly optimal when r is even in that such an induced-universal graph must have at least cn ^r/2 vertices for some c depending only on r.Our construction is explicit in that no probabilistic tools are needed to show that the graph exists or that a given graph is induced-universal. The construction also extends to multigraphs and directed graphs with bounded degree.     

Pkn的均匀全染色

设G(V,E)是一个简单图,f是G的一个k-正常全染色,若f满足||Vi∪Ei|-|Vj∪Ej||≤1(i≠j),其中Vi∪Ei={v|f(v)=i}∪{e|f(e)=i},则称f为G的k-均匀全染色,简记为k-ETC.并称χeT(G)=min{k|G存在k-均匀全染色}为G的均匀全染色数.本文将通过很好的全染色方法得到χeT(Pkn)=5(n≥2k 1),并证明了对Pkn,[5]中猜想是正确的.     

外平面图的全染色与列表全染色

本文证明了,如果G是满足条件Δ(G)≥4的外平面图,则x_T~L(G)=Δ(G) 1,同时对Δ(G)=3给出了XT(G)=Δ(G) 1的简短的新证明,从而蕴含Δ(G)≥3时,XT(G)=Δ(G) 1,其中XT(G)是G的点边全色数,x_T~L(G)是G的点边列表全色数。     

关于图的均匀全色数分类

对一个正常的全染色满足各种颜色所染元素数(点或边)相差不超过1时,称为均匀全染色,其所用最少染色数称为均匀全色数.将图按均匀全色数分类,证明了简单图在若干情况下的均匀全色数定理,得到了一些联图的均匀全色数.     

一些联图的均匀全染色

对-个正常的全染色满足各种颜色所染元素数(点或边)相差不超过1时,称为均匀全染色,其所用最少染色数称为均匀全色数.本文证明了图在若干情况下的均匀全色数定理,得到了Cm VSn,CmVFn和CmVWn的均匀全色数.     

Neighbor Sum Distinguishing Total Choosability of Planar Graphs with Maximum Degree at Least 10

A neighbor sum distinguishing（NSD） total coloring φ of G is a proper total coloring of G such that■ for each edge uv∈E（G）,where E_G（u） is the set of edges incident with a vertex u.In 2015,Pilsniak and Wozniak conjectured that every graph with maximum degree Δ has an NSD total（Δ+3）-coloring.Recently,Yang et al.proved that the conjecture holds for planar graphs with Δ≥ 10,and Qu et al.proved that the list version of the conjecture also holds for planar graphs with Δ≥13.In this paper,we improve their results and prove that the list version of the conjecture holds for planar graphs withΔ≥10.     

Total-coloring of Sparse Graphs with Maximum Degree 6

Acta Mathematicae Applicatae Sinica, English Series - Given a graph G = (V, E) and a positive integer k, a k-total-coloring of G is a mapping φ: V?E → {1, 2, ?, k} such that...     

Bipartite Subgraphs of Graphs with Maximum Degree Three

We prove that for a connected graph G with maximum degree 3 there exists a bipartite subgraph of G containing almost of the edges of G. Furthermore, we completely characterize the set of all extremal graphs, i.e. all connected graphs G=(V, E) with maximum degree 3 for which no bipartite subgraph has more than of the edges; |E| denotes the cardinality of E. For 2-edge-connected graphs there are two kinds of extremal graphs which realize the lower bound . Received: July 17, 1995 / Revised: April 5, 1996     

一些分裂图的点可区别全染色

图G的一个k-正常染色被称为点可区别全染色指任意两点的点及其关联边所染色集合不同.研究了一些分裂图K_(2n+1)\E(K_m)(n≥4,m≥3)的点可区别全色数.     

Maximum Directed Cuts in Graphs with Degree Constraints

The Max Cut problem is an NP-hard problem and has been studied extensively. Alon et?al. (J Graph Theory 55:1–13, 2007) studied a directed version of the Max Cut problem and observed its connection to the Hall ratio of graphs. They proved, among others, that if an acyclic digraph has m edges and each vertex has indegree or outdegree at most 1, then it has a directed cut of size at least 2m/5. Lehel et?al. (J Graph Theory 61:140–156, 2009) extended this result by replacing the “acyclic digraphs” with the “digraphs containing no directed triangles”. In this paper, we characterize the acyclic digraphs with m edges whose maximum dicuts have exactly 2m/5 edges, and our approach gives an alternative proof of the result of Lehel et?al. We also show that there are infinitely many positive rational numbers β < 2/5 for which there exist digraphs D (with directed triangles) such that each vertex of D has indegree or outdegree at most 1, and any maximum directed cut in D has size precisely β|E(D)|.     

On Parsimonious Edge-Colouring of Graphs with Maximum Degree Three

In a graph G of maximum degree Δ, let γ denote the largest fraction of edges that can be Δ edge-coloured. Albertson and Haas showed that ${\gamma \geq \frac{13}{15}}$ when G is cubic. We show here that this result can be extended to graphs with maximum degree 3, with the exception of a graph on 5 vertices. Moreover, there are exactly two graphs with maximum degree 3 (one being obviously the Petersen graph) for which ${\gamma = \frac{13}{15}.}$ This extends a result given by Steffen. These results are obtained by using structural properties of the so called δ-minimum edge colourings for graphs with maximum degree 3.     

若干图的点强全着色

图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的点集的最大顶点数.