Linear 2-Arboricity of Planar Graphs with Neither 3-Cycles Nor Adjacent 4-Cycles

Let G be a planar graph with neither 3-cycles nor adjacent 4-cycles. We prove that if G is connected and δ(G) ≥ 2, then G contains an edge uv with d(u) + d(v) ≤ 7 or a 2-alternating cycle. By this result, we obtain that G’s linear 2-arboricity ${la_{2}(G)\leq\lceil\frac{\Delta(G)+1}{2}\rceil+4.}$ .     

Acyclic Edge Coloring of Planar Graphs Without Small Cycles

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ≤ Δ(G) + 2 for any graphs. In this paper, it is shown that the conjecture holds for planar graphs without 4- and 5-cycles or without 4- and 6-cycles.     

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

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

The Linear Arboricity of Planar Graphs without 5-, 6-Cycles with Chords

The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. In this paper, it is proved that for a planar graph G, ${la(G)=\lceil\frac{\Delta(G)}{2}\rceil}$ if Δ(G) ≥ 7 and G has no 5-cycles with chords, or Δ(G) ≥ 5 and G has no 5-, 6-cycles with chords.     

Additive Coloring of Planar Graphs

An additive coloring of a graph G is an assignment of positive integers \({\{1,2,\ldots ,k\}}\) to the vertices of G such that for every two adjacent vertices the sums of numbers assigned to their neighbors are different. The minimum number k for which there exists an additive coloring of G is denoted by \({\eta (G)}\) . We prove that \({\eta (G) \, \leqslant \, 468}\) for every planar graph G. This improves a previous bound \({\eta (G) \, \leqslant \, 5544}\) due to Norin. The proof uses Combinatorial Nullstellensatz and the coloring number of planar hypergraphs. We also demonstrate that \({\eta (G) \, \leqslant \, 36}\) for 3-colorable planar graphs, and \({\eta (G) \, \leqslant \, 4}\) for every planar graph of girth at least 13. In a group theoretic version of the problem we show that for each \({r \, \geqslant \, 2}\) there is an r-chromatic graph G _r with no additive coloring by elements of any abelian group of order r.     

List Injective Coloring of Planar Graphs

Acta Mathematicae Applicatae Sinica, English Series - A k-coloring of a graph G is a mapping c: V(G) → {1, 2, ?, k}. The coloring c is called injective if any two vertices have a common...     

Oriented Coloring of Triangle-Free Planar Graphs and 2-Outerplanar Graphs

A graph is planar if it can be embedded on the plane without edge-crossings. A graph is 2-outerplanar if it has a planar embedding such that the subgraph obtained by removing the vertices of the external face is outerplanar (i.e. with all its vertices on the external face). An oriented k-coloring of an oriented graph G is a homomorphism from G to an oriented graph H of order k. We prove that every oriented triangle-free planar graph has an oriented chromatic number at most 40, that improves the previous known bound of 47 [Borodin, O. V. and Ivanova, A. O., An oriented colouring of planar graphs with girth at least 4, Sib. Electron. Math. Reports, vol. 2, 239–249, 2005]. We also prove that every oriented 2-outerplanar graph has an oriented chromatic number at most 40, that improves the previous known bound of 67 [Esperet, L. and Ochem, P. Oriented colouring of 2-outerplanar graphs, Inform. Process. Lett., vol. 101(5), 215–219, 2007].     

Fractional Coloring Planar Graphs under Steinberg-type Conditions

Acta Mathematica Sinica, English Series - A Steinberg-type conjecture on circular coloring is recently proposed that for any prime p ≥ 5, every planar graph of girth p without cycles of...     

Coloring Vertices and Faces of Locally Planar Graphs

If G is an embedded graph, a vertex-face r-coloring is a mapping that assigns a color from the set {1, . . . ,r} to every vertex and every face of G such that different colors are assigned whenever two elements are either adjacent or incident. Let χ_vf(G) denote the minimum r such that G has a vertex-face r-coloring. Ringel conjectured that if G is planar, then χ_vf(G)≤6. A graph G drawn on a surface S is said to be 1-embedded in S if every edge crosses at most one other edge. Borodin proved that if G is 1-embedded in the plane, then χ(G)≤6. This result implies Ringel's conjecture. Ringel also stated a Heawood style theorem for 1-embedded graphs. We prove a slight strengthening of this result. If G is 1-embedded in S, let w(G) denote the edge-width of G, i.e. the length of a shortest non-contractible cycle in G. We show that if G is 1-embedded in S and w(G) is large enough, then the list chromatic number ch(G) is at most 8. Work completed while the author was the Neil R. Grabois Visiting Chair of Mathematics, Colgate University, Hamilton, NY 13346 USA. Supported in part by the Ministry of Science and Higher Education of Slovenia, Research Program P1–0507–0101.     

没有5-圈的平面图的BB-染色

设H为G的一个生成子图,（G,H）的一个BB-k-染色是指一个映射f：V（G）→{1,2,…,k},当uv∈E（H）,｜f（u）-f（v）｜≥2;当uv∈E（G）／E（H）,｜f（u）-f（v）｜≥1.定义（G,H）的BB色数x_b（G,H）为最小的整数k,使得（G,H）是BB-k可染的.本文研究了对于任意的连通,非二部平面图G,且G没有5-圈,都存在一棵生成树T,使得x_b（G,T）=4.     

n-Tuple Coloring of Planar Graphs with Large Odd Girth

 The main result of the papzer is that any planar graph with odd girth at least 10k−7 has a homomorphism to the Kneser graph G _k ^{2 k +1}, i.e. each vertex can be colored with k colors from the set {1,2,…,2k+1} so that adjacent vertices have no colors in common. Thus, for example, if the odd girth of a planar graph is at least 13, then the graph has a homomorphism to G ₂ ⁵, also known as the Petersen graph. Other similar results for planar graphs are also obtained with better bounds and additional restrictions. Received: June 14, 1999 Final version received: July 5, 2000     

Coloring Clique-free Graphs in Linear Expected Time

This article presents a linear expected time algorithm to color every graph which does not contain a clique on l + 1 vertices as a subgraph with a minimal number of colors. This extends a result of Dyer and Frieze for l-colorable graphs. For the proof we develop a new method which allows us to precisely estimate the number of graphs with certain structural properties.     

不含相邻三角形的平面图的无圈边着色

An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles.The acyclic edge chromatic number of a graph G is the minimum number k such that there exists an acyclic edge coloring using k colors and is denoted by χ’ a(G).In this paper we prove that χ ’ a(G) ≤(G) + 5 for planar graphs G without adjacent triangles.     

List 2-distance Coloring of Planar Graphs with Girth Five

Acta Mathematicae Applicatae Sinica, English Series - A 2-distance coloring of a graph is a coloring of the vertices such that two vertices at distance at most two receive distinct colors. A list...     

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     

The Linear 2-Arboricity of Planar Graphs

 Let G be a planar graph with maximum degree Δ and girth g. The linear 2-arboricity la ₂(G) of G is the least integer k such that G can be partitioned into k edge-disjoint forests, whose component trees are paths of length at most 2. We prove that (1) la ₂(G)≤⌈(Δ+1)/2⌉+12; (2) la ₂(G)≤⌈(Δ+1)/2⌉+6 if g≥4; (3) la ₂(G)≤⌈(Δ+1)/2⌉+2 if g≥5; (4) la ₂(G)≤⌈(Δ+1)/2⌉+1 if g≥7. Received: June 28, 2001 Final version received: May 17, 2002 Acknowledgments. This work was done while the second and third authors were visiting the Institute of Mathematics, Academia Sinica, Taipei. The financial support provided by the Institute is greatly appreciated.     

一类4-正则平面图的邻点可区别关联色数

所谓图R_n是指具有如下结构的平面图:R_n=(V,E),其中顶点集合V={u_1,u_2,…,u_n}U{v_1,v_2,…,v_n},边集合E={u_iu_(i+1),v_iv_(i+1),u_iv_i,u_iv_(i+1)|i=1,2,…,n},其中u_(n+1)=u_1,v_(n+1)=v_1.通过研究R_n的邻点可区别关联着色,给出了当n=4,n是3或者5的正整数倍时,R_n的邻点可区别关联色数.     

Almost Resolvable Maximum Packings of Complete Graphs with 4-Cycles

If the complete graph K _n has vertex set X, a maximum packing of K _n with 4-cycles, (X, C, L), is an edge-disjoint decomposition of K _n into a collection C of 4-cycles so that the unused edges (the set L) is as small a set as possible. Maximum packings of K _n with 4-cycles were shown to exist by Sch?nheim and Bialostocki (Can. Math. Bull. 18:703–708, 1975). An almost parallel class of a maximum packing (X, C, L) of K _n with 4-cycles is a largest possible collection of vertex disjoint 4-cycles (so with ?/4?{\lfloor/4\rfloor} 4-cycles in it). In this paper, for all orders n, except 9, which does not exist, and possibly 23, 41 and 57, we exhibit a maximum packing of K _n with 4-cycles so that the 4-cycles in the packing are resolvable into almost parallel classes, with any remaining 4-cycles being vertex disjoint. [Note: The three missing orders have now been found, and appear in Billington et al. (to appear).]