Gdk图的平面性和平面图的色数

利用欧拉公式研究了Gdk图的平面性,获得了一个重要定理,并由此得到了关于平面图色数的一个结论.     

若干平面图的完备色数

设G是无割点平面图,X_c(G)为G的点边面完备色数,p=|V(G)|.本文证明了如G为Δ(G)≥7的外平面图,或G为p≥9且Δ(G)≥p-2,或G为Δ(G)≥14的极大平面图,则 X_c(G)=Δ(G)+1.     

外平面图的对策色数

本讨论了图的色对策Ⅱ，给出了外平面图的几个性质，并且利用性质证明了外平面图的对策色数至多是6。     

由圈得到的一类优美图

本文证明了ｎ个顶点的圈增加若干条弦所得到的图优美．     

不含4-,6-圈和相交三角形的平面图的无圈边色数

图G的一个边染色φ:E(G)→{1,2,…,k},若满足任意相邻边都染不同的颜色,且图G不存在双色圈,则称φ为图G的一个无圈k-边染色.图G的无圈边色数χ’_α(G)为使得图G有一个无圈k-边染色的最小正整数k.本文主要证明了对于无4-,6-圈且3-圈与3-圈不相交的平面图G,若Δ(G)≥9,则χ’_α(G)≤Δ(G)+1.     

平面图和系列平行图的无圈边染色

图$G$的正常边染色称为无圈的, 如果图$G$中不含2-色圈, 图$G$的无圈边色数用$a''(G)$表示, 是使图$G$存在正常无圈边染色所需要的最少颜色数. Alon等人猜想: 对简单图$G$, 有$a''(G)\leq{\Delta(G)+2}$. 设图$G$是围长为$g(G)$的平面图, 本文证明了: 如果$g(G)\geq3$, 则$a''(G)\leq\max\{2\Delta(G)-2,\Delta(G)+22\}$; 如果 $g(G)\geq5$, 则$a''(G)\leq{\Delta(G)+2}$; 如果$g(G)\geq7$, 则$a''(G)\leq{\Delta(G)+1}$; 如果$g(G)\geq16$并且$\Delta(G)\geq3$, 则$a''(G)=\Delta(G)$; 对系列平行图$G$, 有$a''(G)\leq{\Delta(G)+1}$.     

2-外平面图的无圈边色数

一个图G的无圈边染色是一个止常的边染色使得其不产生双色圈．Alon,Sudakov和Zaks（2001）猜想：每一个简单图G是无到（△（G）＋2）-边可染的,其中△（G）是G的最大度．本文对2-外平面图族证明了该猜想成立．     

外平面图的对策色数

本文讨论了图的色对策 ,给出了外平面图的几个性质 ,并且利用性质证明了外平面图的对策色数至多是 6     

平面图线性色数的一个上界

如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色．图G的线性色数用lc（G）表示,是指G的所有线性染色中所用的最少颜色的个数．证明了：若G是一个最大度△（G）≠5,6的平面图,则lc（G）≤2△（G）．     

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.     

On total chromatic number of planar graphs without 4-cycles

Let G be a simple graph with maximum degree A(G) and total chromatic number Xve(G). Vizing conjectured thatΔ(G) 1≤Xve(G)≤Δ(G) 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not been settled yet. The unsettled difficult case for planar graphs isΔ(G) = 6. This paper shows that if G is a simple planar graph with maximum degree 6 and without 4-cycles, then Xve(G)≤8. Together with the previous results on this topic, this shows that every simple planar graph without 4-cycles satisfies the Total Chromatic Conjecture.     

Total chromatic number of planar graphs with maximum degree ten

In this article we prove that the total chromatic number of a planar graph with maximum degree 10 is 11. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 91–102, 2007     

Star chromatic numbers of some planar graphs

The concept of the star chromatic number of a graph was introduced by Vince (A. Vince, Star chromatic number, J. Graph Theory 12 (1988), 551–559), which is a natural generalization of the chromatic number of a graph. This paper calculates the star chromatic numbers of three infinite families of planar graphs. More precisely, the first family of planar graphs has star chromatic numbers consisting of two alternating infinite decreasing sequences between 3 and 4; the second family of planar graphs has star chromatic numbers forming an infinite decreasing sequence between 3 and 4; and the third family of planar graphs has star chromatic number 7/2. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 33–42, 1998     

The number of defective colorings of graphs on surfaces

A (k, 1)‐coloring of a graph is a vertex‐coloring with k colors such that each vertex is permitted at most 1 neighbor of the same color. We show that every planar graph has at least cρⁿ distinct (4, 1)‐colorings, where c is constant and ρ≈1.466 satisfies ρ³ = ρ² + 1. On the other hand for any ε>0, we give examples of planar graphs with fewer than c(? + ε)ⁿ distinct (4, 1)‐colorings, where c is constant and . Let γ(S) denote the chromatic number of a surface S. For every surface S except the sphere, we show that there exists a constant c′ = c′(S)>0 such that every graph embeddable in S has at least c′2ⁿ distinct (γ(S), 1)‐colorings. © 2010 Wiley Periodicals, Inc. J Graph Theory 28:129‐136, 2011     

Characterizing planarity using theta graphs

A theta graph is a homeomorph of K_2,3. In an embedded planar graph the local rotation at one degree-three vertex of a theta graph determines the local rotation at the other degree-three vertex. Using this observation, we give a characterization of planar graphs in terms of balance in an associated signed graph whose vertices are K_1,3 subgraphs and whose edges correspond to theta graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 17–20, 1998