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

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

围长至少为6的平面图的邻点可区别边染色

邻点可区别边染色是指图G有一个正常边染色且任意两个相邻顶点的颜色集合不相等.邻点可区别边色数是指使图G有一个邻点可区别边染色的最小颜色数值,记作χ_α’(G).本文证明了:若图G是围长至少为6的正常平面图,则有χ_α’(G)≤max{6,△(G)+1}.     

平面图的单射边染色

图G的k-单射边染色是指映射f:E(G)→{1,2,…,k},若e₁,e₂和e₃是G中的连续边,则f (e₁)≠f(e₃).称χ’_i(G)=min{k|G存在k-单射边染色}为图的单射边染色数.本文证明了:对g(G)≥6的平面图G,有χ’_i(G)≤3Δ(G)-2,对g(G)≥26且Δ(G)≤3的平面图G,有χ’_i(G)≤4,对g(G)≥16且Δ(G)≥4的平面图G,有χ’_i(G)≤Δ(G)+1,其中g(G)表示平面图G的围长.     

围长不小于6且最大度至少为8的平面图的无圈列表边染色

对图G的一个正常边染色,如果图G的任何一个圈至少染三种颜色,则称这个染色为无圈边染色.若L为图G的一个边列表,对图G的一个无圈边染色φ,如果对任意e∈E(G)都有ф(e)∈L(e),则称ф为无圈L-边染色.用a′_(list)(G)表示图G的无圈列表边色数.证明若图G是一个平面图,且它的最大度△≥8,围长g(G)≥6,则a′_(list)(G)=△.     

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

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

围长至少为4的平面图的邻点可区别边色数

图G的邻点可区别边染色是G的正常边染色,使得每一对相邻顶点有不同的颜色集合．G的邻点可区别边色数X＇a（G）是使得G有一个k-邻点可区别边染色的最小正整数七．本文证明了：若G是围长至少为4且最大度至少为6的平面图,则X＇a（G）≤△＋2．     

平面图的强边染色

图$G$的强边染色是在正常边染色的基础上, 要求距离不超过$2$的任意两条边染不同的颜色, 强边染色所用颜色的最小整数称为图$G$的强边色数。本文首先给出极小反例的构型, 然后通过权转移法, 证明了$g(G)\geq5$, $\Delta(G)\geq6$且$5$-圈不相交的平面图的强边色数至多是$4\Delta(G)-1$。     

平面图的强边染色

图$G$的强边染色是在正常边染色的基础上, 要求距离不超过$2$的任意两条边染不同的颜色, 强边染色所用颜色的最小整数称为图$G$的强边色数。本文首先给出极小反例的构型, 然后通过权转移法, 证明了$g(G)\geq5$, $\Delta(G)\geq6$且$5$-圈不相交的平面图的强边色数至多是$4\Delta(G)-1$。     

划分围长至少为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\}$.     

围长至少为5的IC-可平面图的邻点可区别边染色

给图G一个正常k-边染色φ,对G的任意两个相邻的顶点u和v,若满足与u关联的边所染颜色集合和与v关联的边所染颜色的集合不同,则称φ为图G的k-邻点可区别边染色.用χ’_a(G)表示图G的邻点可区别边色数,即使得G有一个k-邻点可区别边染色的最小正整数k.通过运用权转移方法研究围长至少为5的正常IC-可平面图的邻点可区别边染色,得到了χ’_a(G)≤max{Δ(G)+2,11}.     

Linear coloring of planar graphs with large girth

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number of the graph G is the smallest number of colors in a linear coloring of G. In this paper we prove that every planar graph G with girth g and maximum degree Δ has if G satisfies one of the following four conditions: (1) g≥13 and Δ≥3; (2) g≥11 and Δ≥5; (3) g≥9 and Δ≥7; (4) g≥7 and Δ≥13. Moreover, we give better upper bounds of linear chromatic number for planar graphs with girth 5 or 6.     

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.     

没有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.     

Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths

Recently, Borodin, Kostochka, and Yancey (Discrete Math 313(22) (2013), 2638–2649) showed that the vertices of each planar graph of girth at least 7 can be 2‐colored so that each color class induces a subgraph of a matching. We prove that any planar graph of girth at least 6 admits a vertex coloring in colors such that each monochromatic component is a path of length at most 14. Moreover, we show a list version of this result. On the other hand, for each positive integer , we construct a planar graph of girth 4 such that in any coloring of vertices in colors there is a monochromatic path of length at least t. It remains open whether each planar graph of girth 5 admits a 2‐coloring with no long monochromatic paths.     

An oriented coloring of planar graphs with girth at least five

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 graph with a maximum average degree less than and girth at least 5 has an oriented chromatic number at most 16. This implies that every oriented planar graph with girth at least 5 has an oriented chromatic number at most 16, that improves the previous known bound of 19 due to Borodin et al. [O.V. Borodin, A.V. Kostochka, J. Nešet?il, A. Raspaud, É. Sopena, On the maximum average degree and the oriented chromatic number of a graph, Discrete Math. 206 (1999) 77-89].     

Linear choosability of sparse graphs

A linear coloring is a proper coloring such that each pair of color classes induces a union of disjoint paths. We study the linear list chromatic number, denoted , of sparse graphs. The maximum average degree of a graph G, denoted mad(G), is the maximum of the average degrees of all subgraphs of G. It is clear that any graph G with maximum degree Δ(G) satisfies . In this paper, we prove the following results: (1) if and Δ(G)≥3, then , and we give an infinite family of examples to show that this result is best possible; (2) if and Δ(G)≥9, then , and we give an infinite family of examples to show that the bound on cannot be increased in general; (3) if G is planar and has girth at least 5, then .     

(1, k)‐Coloring of Graphs with Girth at Least Five on a Surface

A graph is ‐colorable if its vertex set can be partitioned into r sets so that the maximum degree of the graph induced by is at most for each . For a given pair , the question of determining the minimum such that planar graphs with girth at least g are ‐colorable has attracted much interest. The finiteness of was known for all cases except when . Montassier and Ochem explicitly asked if d₂(5, 1) is finite. We answer this question in the affirmative with ; namely, we prove that all planar graphs with girth at least five are (1, 10)‐colorable. Moreover, our proof extends to the statement that for any surface S of Euler genus γ, there exists a where graphs with girth at least five that are embeddable on S are (1, K)‐colorable. On the other hand, there is no finite k where planar graphs (and thus embeddable on any surface) with girth at least five are (0, k)‐colorable.     

Upper bounds on the linear chromatic number of a graph

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is a union of vertex-disjoint paths. The linear chromatic number of G is the smallest number of colors in a linear coloring of G.Let G be a graph with maximum degree Δ(G). In this paper we prove the following results: (1) ; (2) if Δ(G)≤4; (3) if Δ(G)≤5; (4) if G is planar and Δ(G)≥52.