The relaxed game chromatic number of outerplanar graphs

The (r,d)‐relaxed coloring game is played by two players, Alice and Bob, on a graph G with a set of r colors. The players take turns coloring uncolored vertices with legal colors. A color α is legal for an uncolored vertex u if u is adjacent to at most d vertices that have already been colored with α, and every neighbor of u that has already been colored with α is adjacent to at most d – 1 vertices that have already been colored with α. Alice wins the game if eventually all the vertices are legally colored; otherwise, Bob wins the game when there comes a time when there is no legal move left. We show that if G is outerplanar then Alice can win the (2,8)‐relaxed coloring game on G. It is known that there exists an outerplanar graph G such that Bob can win the (2,4)‐relaxed coloring game on G. © 2004 Wiley Periodicals, Inc. J Graph Theory 46:69–78, 2004     

Acyclic edge colorings of graphs

A proper coloring of the edges 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. For certain graphs G, a′(G) ≥ Δ(G) + 2 where Δ(G) is the maximum degree in G. It is known that a′(G) ≤ 16 Δ(G) for any graph G. We prove that there exists a constant c such that a′(G) ≤ Δ(G) + 2 for any graph G whose girth is at least cΔ(G) log Δ(G), and conjecture that this upper bound for a′(G) holds for all graphs G. We also show that a′(G) ≤ Δ + 2 for almost all Δ‐regular graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 157–167, 2001     

Game chromatic number of outerplanar graphs

This note proves that the game chromatic number of an outerplanar graph is at most 7. This improves the previous known upper bound of the game chromatic number of outerplanar graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 67–70, 1999     

Acyclic edge coloring of planar graphs without adjacent cycles

A proper edge coloring of a graph G is said to be acyclic if there is no bicolored cycle in G.The acyclic edge chromatic number of G,denoted byχ′a(G),is the smallest number of colors in an acyclic edge coloring of G.Let G be a planar graph with maximum degree.In this paper,we show thatχ′a(G)+2,if G has no adjacent i-and j-cycles for any i,j∈{3,4,5},which implies a result of Hou,Liu and Wu(2012);andχ′a(G)+3,if G has no adjacent i-and j-cycles for any i,j∈{3,4,6}.     

The generalized acyclic edge chromatic number of random regular graphs

The r‐acyclic edge chromatic number of a graph is defined to be the minimum number of colors required to produce an edge coloring of the graph such that adjacent edges receive different colors and every cycle C has at least min(|C|, r) colors. We show that (r ? 2)d is asymptotically almost surely (a.a.s.) an upper bound on the r‐acyclic edge chromatic number of a random d‐regular graph, for all constants r ≥ 4 and d ≥ 2. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 101–125, 2006     

不含5-圈的平面图的无圈边着色

图G的一个无圈边着色是一个正常的边着色且不含双色的圈.图G的无圈边色数是图G的无圈边着色中所用色数的最小者.本文用反证法得到了不含5-圈的平面图G的无圈边色数的一个上界.     

Acyclic edge coloring of graphs with maximum degree 4

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 that for any simple and finite graph G, a′(G)?Δ + 2, where Δ=Δ(G) denotes the maximum degree of G. We prove the conjecture for connected graphs with Δ(G)?4, with the additional restriction that m?2n?1, where n is the number of vertices and m is the number of edges in G. Note that for any graph G, m?2n, when Δ(G)?4. It follows that for any graph G if Δ(G)?4, then a′(G)?7. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 192–209, 2009     

没有K4-图子式的图的无圈边色数

一个图G 的无圈k- 边染色是指G 的一个正常的不产生双色圈的k- 边染色. G 的无圈边色数a′(G) 定义为使得G 有一个无圈k- 边染色的最小的整数k. 本文完全刻画了最大度不为4 的没有K₄-图子式的图的无圈边色数.     

Acyclic edge coloring of triangle-free 1-planar graphs

A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by χ a(G), is the least number of colors such that G has an acyclic edge coloring. A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that χ a(G) ≤Δ(G) + 22, if G is a triangle-free 1-planar graph.     

Acyclic edge colorings of planar graphs and seriesparallel graphs

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. For planar graphs G with girth g(G), we prove that a′(G) ⩽ max{2Δ(G) − 2, Δ(G) + 22} if g(G) ⩾ 3, a′(G) ⩽ Δ(G) + 2 if g(G) ⩾ 5, a′(G) ⩽ Δ(G) + 1 if g(G) ⩾ 7, and a′(G) = Δ(G) if g(G) ⩾ 16 and Δ(G) ⩾ 3. For series-parallel graphs G, we have a′(G) ⩽ Δ(G) + 1. This work was supported by National Natural Science Foundation of China (Grant No. 10871119) and Natural Science Foundation of Shandong Province (Grant No. Y2008A20).     

Acyclic List Edge Coloring of Graphs

A proper edge coloring of a graph is said to be acyclic if any cycle is colored with at least three colors. An edge-list L of a graph G is a mapping that assigns a finite set of positive integers to each edge of G. An acyclic edge coloring ? of G such that for any is called an acyclic L-edge coloring of G. A graph G is said to be acyclically k-edge choosable if it has an acyclic L‐edge coloring for any edge‐list L that satisfies for each edge e. The acyclic list chromatic index is the least integer k such that G is acyclically k‐edge choosable. We develop techniques to obtain bounds for the acyclic list chromatic indices of outerplanar graphs, subcubic graphs, and subdivisions of Halin graphs.     

Edge‐face chromatic number and edge chromatic number of simple plane graphs

Given a simple plane graph G, an edge‐face k‐coloring of G is a function ? : E(G) ∪ F(G) → {1,…,k} such that, for any two adjacent or incident elements a, b ∈ E(G) ∪ F(G), ?(a) ≠ ?(b). Let χ_e(G), χ_ef(G), and Δ(G) denote the edge chromatic number, the edge‐face chromatic number, and the maximum degree of G, respectively. In this paper, we prove that χ_ef(G) = χ_e(G) = Δ(G) for any 2‐connected simple plane graph G with Δ (G) ≥ 24. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Proper orientation number of triangle-free bridgeless outerplanar graphs

An orientation of $G$ is a digraph obtained from $G$ by replacing each edge by exactly one of two possible arcs with the same endpoints. We call an orientation proper if neighboring vertices have different in-degrees. The proper orientation number of a graph $G$, denoted by $\overrightarrow{\chi }\left(G\right)$, is the minimum maximum in-degree of a proper orientation of $G$. Araujo et al asked whether there is a constant $c$ such that $\text{◂≤▸}\overrightarrow{\chi }\left(G\right)\le c$ for every outerplanar graph $G$ and showed that $\text{◂≤▸}\overrightarrow{\chi }\left(G\right)\le 7$ for every cactus $G$. We prove that $\text{◂≤▸}\overrightarrow{\chi }\left(G\right)\le 3$ if $G$ is a triangle-free 2-connected outerplanar graph and $\text{◂≤▸}\overrightarrow{\chi }\left(G\right)\le 4$ if $G$ is a triangle-free bridgeless outerplanar graph.     

Acyclic chromatic indices of planar graphs with large girth

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index a^′(G) of G is the smallest k such that G has an acyclic edge coloring using k colors.In this paper, we prove that every planar graph G with girth g(G) and maximum degree Δ has a^′(G)=Δ if there exists a pair (k,m)∈{(3,11),(4,8),(5,7),(8,6)} such that G satisfies Δ≥k and g(G)≥m.     

CHROMATIC NUMBER OF SQUARE OF MAXIMAL OUTERPLANAR GRAPHS

Let x（G^2） denote the chromatic number of the square of a maximal outerplanar graph G and Q denote a maximal outerplanar graph obtained by adding three chords y1 y3, y3y5, y5y1 to a 6-cycle y1y2…y6y1. In this paper, it is proved that △ ＋ 1 ≤ x（G^2） ≤△ ＋ 2, and x（G^2） = A ＋ 2 if and only if G is Q, where A represents the maximum degree of G.     

Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs

For a finite simple edge-colored connected graph G (the coloring may not be proper), a rainbow path in G is a path without two edges colored the same; G is rainbow connected if for any two vertices of G, there is a rainbow path connecting them. Rainbow connection number, rc(G), of G is the minimum number of colors needed to color its edges such that G is rainbow connected. Chakraborty et al. (2011) [5] proved that computing rc(G) is NP-hard and deciding if rc(G)=2 is NP-complete. When edges of G are colored with fixed number k of colors, Kratochvil [6] proposed a question: what is the complexity of deciding whether G is rainbow connected? is this an FPT problem? In this paper, we prove that any maximal outerplanar graph is k rainbow connected for suitably large k and can be given a rainbow coloring in polynomial time.     

外平面图的弱完备染色

假设G=（V,E,F）是一个平面图。如果e₁和e₂是G中两条相邻边且在关联的面的边界上连续出现,那么称e₁和e₂面相邻。图G的一个弱完备k-染色是指存在一个从V ∪ E ∪ F到k色集合{1, …, K}的映射,使得任意两个相邻点,两个相邻面,两条面相邻的边,以及V ∪ E ∪ F中任意两个相关联的元素都染不同的颜色。若图G有一个弱完备k-染色,则称G是弱完备k-可染的。平面图G的弱完备色数是指G是弱完备k-可染的正整数k的最小值,记成χ_vef（G）。2016年,Fabrici等人猜想：每个无环且无割边的连通平面图是弱完备7-可染的。证明外平面图满足猜想,即外平面图是弱完备7-可染的。     

The chromatic number of oriented graphs

We introduce in this paper the notion of the chromatic number of an oriented graph G (that is of an antisymmetric directed graph) defined as the minimum order of an oriented graph H such that G admits a homomorphism to H. We study the chromatic number of oriented k-trees and of oriented graphs with bounded degree. We show that there exist oriented k-trees with chromatic number at least 2^k+1 - 1 and that every oriented k-tree has chromatic number at most (k + 1) × 2^k. For 2-trees and 3-trees we decrease these upper bounds respectively to 7 and 16 and show that these new bounds are tight. As a particular case, we obtain that oriented outerplanar graphs have chromatic number at most 7 and that this bound is tight too. We then show that every oriented graph with maximum degree k has chromatic number at most (2k - 1) × 2^2k-2. For oriented graphs with maximum degree 2 we decrease this bound to 5 and show that this new bound is tight. For oriented graphs with maximum degree 3 we decrease this bound to 16 and conjecture that there exists no such connected graph with chromatic number greater than 7. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 191–205, 1997     

Acyclic edge coloring of 2‐degenerate 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). A graph is called 2‐degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2‐degenerate graphs properly contains series–parallel graphs, outerplanar graphs, non ? regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. 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. We prove the conjecture for 2‐degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2‐degenerate graph with maximum degree Δ, then a′(G)?Δ + 1. © 2010 Wiley Periodicals, Inc. J Graph Theory 69: 1–27, 2012     

Acyclic 6-choosability of planar graphs without adjacent short cycles

A proper vertex coloring of a graph G is acyclic if G contains no bicolored cycles.Given a list assignment L={L(v)|v∈V}of G,we say that G is acyclically L-colorable if there exists a proper acyclic coloringπof G such thatπ(v)∈L(v)for all v∈V.If G is acyclically L-colorable for any list assignment L with|L(v)|k for all v∈V(G),then G is acyclically k-choosable.In this paper,we prove that every planar graph G is acyclically 6-choosable if G does not contain 4-cycles adjacent to i-cycles for each i∈{3,4,5,6}.This improves the result by Wang and Chen(2009).