围长至少是7的1-平面图是$(1,1,1,0)$-可染的

一个图称为是1-平面图的, 如果它可以画在一个平面上使得它的每条边最多交叉另外一条边.本文证明了围长大于等于7的1-平面图是$(1,1,1,0)$-可染的.     

围长至少为5的平面图的线性染色

如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数本文证明了对于每一个最大度为△(G)且围长至少为5的平面图G有lc(G)≤[△(G)/2]+5,并且当△(G)∈{7,8,…,14...     

Improper Coloring of Sparse Graphs with a Given Girth,II: Constructions

A graph G is ‐colorable if can be partitioned into two sets and so that the maximum degree of is at most j and of is at most k. While the problem of verifying whether a graph is (0, 0)‐colorable is easy, the similar problem with in place of (0, 0) is NP‐complete for all nonnegative j and k with . Let denote the supremum of all x such that for some constant every graph G with girth g and for every is ‐colorable. It was proved recently that . In a companion paper, we find the exact value . In this article, we show that increasing g from 5 further on does not increase much. Our constructions show that for every g, . We also find exact values of for all g and all .     

On total 9‐coloring planar graphs of maximum degree seven

Given a graph G, a total k‐coloring of G is a simultaneous coloring of the vertices and edges of G with at most k colors. If Δ(G) is the maximum degree of G, then no graph has a total Δ‐coloring, but Vizing conjectured that every graph has a total (Δ + 2)‐coloring. This Total Coloring Conjecture remains open even for planar graphs. This article proves one of the two remaining planar cases, showing that every planar (and projective) graph with Δ ≤ 7 has a total 9‐coloring by means of the discharging method. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 67–73, 1999     

On the Minimum Edge‐Density of 4‐Critical Graphs of Girth Five

In a recent seminal work, Kostochka and Yancey proved that for every 4‐critical graph G. In this article, we prove that for every 4‐critical graph G with girth at least five. When combined with another result of the second author, the improvement on the constant term leads to a corollary that there exist such that for every 4‐critical graph G with girth at least five. Moreover, it provides a unified and shorter proof of both a result of Thomassen and a result of Thomas and Walls without invoking any topological property, where the former proves that every graph with girth five embeddable in the projective plane or torus is 3‐colorable, and the latter proves the same for the Klein bottle.     

Improper coloring of graphs on surfaces

A graph is -colorable if its vertex set can be partitioned into sets , such that for each , the subgraph of induced by has maximum degree at most . The Four Color Theorem states that every planar graph is -colorable, and a classical result of Cowen, Cowen, and Woodall shows that every planar graph is -colorable. In this paper, we extend both of these results to graphs on surfaces. Namely, we show that every graph embeddable on a surface of Euler genus is -colorable and -colorable. Moreover, these graphs are also -colorable and -colorable. We also prove that every triangle-free graph that is embeddable on a surface of Euler genus is -colorable. This is an extension of Grötzsch's Theorem, which states that triangle-free planar graphs are -colorable. Finally, we prove that every graph of girth at least 7 that is embeddable on a surface of Euler genus is -colorable. All these results are best possible in several ways as the girth condition is sharp, the constant maximum degrees cannot be improved, and the bounds on the maximum degrees depending on are tight up to a constant multiplicative factor.     

6‐Star‐Coloring of Subcubic Graphs

A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two adjacent vertices are assigned the same color) such that no path on four vertices is 2‐colored. The star chromatic number of G is the smallest integer k for which G admits a star coloring with k colors. In this paper, we prove that every subcubic graph is 6‐star‐colorable. Moreover, the upper bound 6 is best possible, based on the example constructed by Fertin, Raspaud, and Reed (J Graph Theory 47(3) (2004), 140–153).     

Exponentially many 4‐list‐colorings of triangle‐free graphs on surfaces

Thomassen proved that every planar graph G on n vertices has at least distinct L‐colorings if L is a 5‐list‐assignment for G and at least distinct L‐colorings if L is a 3‐list‐assignment for G and G has girth at least five. Postle and Thomas proved that if G is a graph on n vertices embedded on a surface Σ of genus g, then there exist constants such that if G has an L‐coloring, then G has at least distinct L‐colorings if L is a 5‐list‐assignment for G or if L is a 3‐list‐assignment for G and G has girth at least five. More generally, they proved that there exist constants such that if G is a graph on n vertices embedded in a surface Σ of fixed genus g, H is a proper subgraph of G, and ϕ is an L‐coloring of H that extends to an L‐coloring of G, then ϕ extends to at least distinct L‐colorings of G if L is a 5‐list‐assignment or if L is a 3‐list‐assignment and G has girth at least five. We prove the same result if G is triangle‐free and L is a 4‐list‐assignment of G, where , and .     

Edge Coloring of Embedded Graphs with Large Girth

Let G be a simple graph embedded in the surface of Euler characteristic ()0. Denote _e(G), and g the edge chromatic number, the maximum degree and the girth of the graph G, respectively. The paper shows that _e(G)= if 5 and g4, or 4 and g5, or 3 and g9. In addition, if ()>0, then _e(G)= if 3 and g8. Acknowledgments.The authors would like to thank Dr. C.Q. Zhang for carefully reading several versions of this paper during its preparation and for suggesting several stylistic changes that have improved the overall presentation.     

2‐Distance Coloring of Sparse Graphs

For graphs of bounded maximum average degree, we consider the problem of 2‐distance coloring, that is, the problem of coloring the vertices while ensuring that two vertices that are adjacent or have a common neighbor receive different colors. We prove that graphs with maximum average degree less than and maximum degree Δ at least 4 are 2‐distance ‐colorable, which is optimal and improves previous results from Dolama and Sopena, and from Borodin et al. We also prove that graphs with maximum average degree less than (resp. , ) and maximum degree Δ at least 5 (resp. 6, 8) are list 2‐distance ‐colorable, which improves previous results from Borodin et al., and from Ivanova. We prove that any graph with maximum average degree m less than and with large enough maximum degree Δ (depending only on m) can be list 2‐distance ‐colored. There exist graphs with arbitrarily large maximum degree and maximum average degree less than 3 that cannot be 2‐distance ‐colored: the question of what happens between and 3 remains open. We prove also that any graph with maximum average degree can be list 2‐distance ‐colored (C depending only on m). It is optimal as there exist graphs with arbitrarily large maximum degree and maximum average degree less than 4 that cannot be 2‐distance colored with less than colors. Most of the above results can be transposed to injective list coloring with one color less.     

3‐Coloring Triangle‐Free Planar Graphs with a Precolored 8‐Cycle

Let G be a planar triangle‐free graph and let C be a cycle in G of length at most 8. We characterize all situations where a 3‐coloring of C does not extend to a proper 3‐coloring of the whole graph.     

Acyclic Edge Coloring of Triangle‐Free Planar Graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G) ? Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. If every induced subgraph H of G satisfies the condition |E(H)| ? 2|V(H)|?1, we say that the graph G satisfies Property A. In this article, we prove that if G satisfies Property A, then a′(G) ? Δ + 3. Triangle‐free planar graphs satisfy Property A. We infer that a′(G) ? Δ + 3, if G is a triangle‐free planar graph. Another class of graph which satisfies Property A is 2‐fold graphs (union of two forests). © 2011 Wiley Periodicals, Inc. J Graph Theory     

Coloring of Plane Graphs with Unique Maximal Colors on Faces

The Four Color Theorem asserts that the vertices of every plane graph can be properly colored with four colors. Fabrici and Göring conjectured the following stronger statement to also hold: the vertices of every plane graph can be properly colored with the numbers 1, …, 4 in such a way that every face contains a unique vertex colored with the maximal color appearing on that face. They proved that every plane graph has such a coloring with the numbers 1, …, 6. We prove that every plane graph has such a coloring with the numbers 1, …, 5 and we also prove the list variant of the statement for lists of sizes seven.     

4‐Coloring P6‐Free Graphs with No Induced 5‐Cycles

We show that the 4‐coloring problem can be solved in polynomial time for graphs with no induced 5‐cycle C₅ and no induced 6‐vertex path P₆     

Plane Graphs with Maximum Degree Are Entirely ‐Colorable

Let be a plane graph with the sets of vertices, edges, and faces V, E, and F, respectively. If one can color all elements in using k colors so that any two adjacent or incident elements receive distinct colors, then G is said to be entirely k‐colorable. Kronk and Mitchem [Discrete Math 5 (1973) 253‐260] conjectured that every plane graph with maximum degree Δ is entirely ‐colorable. This conjecture has now been settled in Wang and Zhu (J Combin Theory Ser B 101 (2011) 490–501), where the authors asked: is every simple plane graph entirely ‐colorable? In this article, we prove that every simple plane graph with is entirely ‐colorable, and conjecture that every simple plane graph, except the tetrahedron, is entirely ‐colorable.     

划分围长至少为6 的平面图为有界大小的分支

图$G$的$(\mathcal{O}_{k_1}, \mathcal{O}_{k_2})$-划分是将$V(G)$划分成两个非空子集$V_{1}$和$V_{2}$, 使得$G[V_{1}]$和$G[V_{2}]$分别是分支的阶数至多$k_1$和$k_2$的图.在本文中,我们考虑了有围长限制的平面图的点集划分问题,使得每个部分导出一个具有有界大小分支的图.我们证明了每一个围长至少为6并且$i$-圈不与$j$-圈相交的平面图允许$(\mathcal{O}_{2}$, $\mathcal{O}_{3})$-划分,其中$i\in\{6,7,8\}$和$j\in\{6,7,8,9\}$.     

The symmetric (2k,k)‐graphs

A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K_{2k + 2} − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001     

若干笛卡尔积图的邻点可区别E-全染色

图G(V,E)的k是一个正整数,f是V(G)∪E(G)到{1,2,…,k}的一个映射,如果u,v∈V(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.得到了Pm×Pn,Pm×Cn,Cm×Cn的邻点可区别E-全色数,其中C(u)={f(u)}∪{f(uv)uv∈E(G)}.     

Acyclic Chromatic Indices of Planar Graphs with Girth At Least 4

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index of G is the smallest integer k such that G has an acyclic edge coloring using k colors. Fiamik (Math. Slovaca 28 (1978), 139–145) and later Alon et al. (J Graph Theory 37 (2001), 157–167) conjectured that for any simple graph G with maximum degree Δ. In this article, we confirm this conjecture for planar graphs of girth at least 4.