Acyclic list 7‐coloring of planar graphs

The acyclic list chromatic number of every planar graph is proved to be at most 7. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 83–90, 2002     

Star coloring bipartite planar graphs

A star coloring of a graph is a proper vertex‐coloring such that no path on four vertices is 2‐colored. We prove that the vertices of every bipartite planar graph can be star colored from lists of size 14, and we give an example of a bipartite planar graph that requires at least eight colors to star color. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 1–10, 2009     

List coloring triangle-free planar graphs

This paper proves the following result. Assume $G$ is a triangle-free planar graph, $X$ is an independent set of $G$. If $L$ is a list assignment of $G$ such that $\text{◂=▸}|L\left(v\right)|=4$ for each vertex $\text{◂+▸}v\in V\left(G\right)-X$ and $\text{◂=▸}|L\left(v\right)|=3$ for each vertex $v\in X$, then $G$ is $L$-colorable.     

Minor‐universal planar graphs without accumulation points

We show that the countably infinite union of infinite grids, H say, is minor‐universal in the class of all graphs that can be drawn in the plane without vertex accumulation points, i.e., that H contains every such graph as a minor. Furthermore, we characterize the graphs that occur as minors of the infinite grid by a natural topological condition on their embeddings. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 1–7, 2001     

Total colorings of planar graphs with large maximum degree

It is proved that a planar graph with maximum degree Δ ≥ 11 has total (vertex-edge) chromatic number $Delta; + 1. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 53–59, 1997     

Extending colorings of locally planar graphs

Suppose G is a graph embedded in S_g with width (also known as edge width) at least 264(2^g−1). If P ⊆ V(G) is such that the distance between any two vertices in P is at least 16, then any 5‐coloring of P extends to a 5‐coloring of all of G. We present similar extension theorems for 6‐ and 7‐chromatic toroidal graphs, for 3‐colorable large‐width graphs embedded on S_g with every face even‐sided, and for 4‐colorable large‐width Eulerian triangulations. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 105–116, 2001     

Edge‐partitions of planar graphs and their game coloring numbers

Let G be a planar graph and let g(G) and Δ(G) be its girth and maximum degree, respectively. We show that G has an edge‐partition into a forest and a subgraph H so that (i) Δ(H) ≤ 4 if g(G) ≥ 5; (ii) Δ(H) ≤ 2 if g(G) ≥ 7; (iii) Δ(H)≤ 1 if g(G) ≥ 11; (iv) Δ(H) ≤ 7 if G does not contain 4‐cycles (though it may contain 3‐cycles). These results are applied to find the following upper bounds for the game coloring number col_g(G) of a planar graph G: (i) col_g(G) ≤ 8 if g(G) ≥ 5; (ii) col_g(G)≤ 6 if g(G) ≥ 7; (iii) col_g(G) ≤ 5 if g(G) ≥ 11; (iv) col_g(G) ≤ 11 if G does not contain 4‐cycles (though it may contain 3‐cycles). © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 307–317, 2002     

Group edge choosability of planar graphs without adjacent short cycles

In this paper,we prove that 2-degenerate graphs and some planar graphs without adjacent short cycles are group(Δ(G)+1)-edge-choosable,and some planar graphs with large girth and maximum degree are groupΔ(G)-edge-choosable.     

Planar graphs with neither 5‐cycles nor close 3‐cycles are 3‐colorable

In 2003, O. V. Borodin and A. Raspaud conjectured that every planar graph with the minimum distance between triangles, d_Δ, at least 1 and without 5‐cycles is 3‐colorable. This Bordeaux conjecture (Brdx3CC) has common features with Havel's (1970) and Steinberg's (1976) 3‐color problems. A relaxation of Brdx3CC with d_Δ?4 was confirmed in 2003 by Borodin and Raspaud, whose result was improved to d_Δ?3 by Borodin and A. N. Glebov (2004) and, independently, by B. Xu (2007). The purpose of this article is to make the penultimate step (d_Δ?2) towards Brdx3CC. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 1–31, 2010     

(2 + ϵ)‐Coloring of planar graphs with large odd‐girth

The odd‐girth of a graph is the length of a shortest odd circuit. A conjecture by Pavol Hell about circular coloring is solved in this article by showing that there is a function ƒ(ϵ) for each ϵ : 0 < ϵ < 1 such that, if the odd‐girth of a planar graph G is at least ƒ(ϵ), then G is (2 + ϵ)‐colorable. Note that the function ƒ(ϵ) is independent of the graph G and ϵ → 0 if and only if ƒ(ϵ) → ∞. A key lemma, called the folding lemma, is proved that provides a reduction method, which maintains the odd‐girth of planar graphs. This lemma is expected to have applications in related problems. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 109–119, 2000     

Spanning maximal planar subgraphs of random graphs

We study the threshold for the existence of a spanning maximal planar subgraph in the random graph G_{n, p} . We show that it is very near p = 1/n^? We also discuss the threshold for the existence of a spanning maximal outerplanar subgraph. This is very near p = 1/n^½.     

Acyclic 5‐choosability of planar graphs without small cycles

A proper vertex coloring of a graph G = (V,E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L‐list colorable if for a given list assignment L = {L(v): v: ∈ V}, there exists a proper acyclic coloring ? of G such that ?(v) ∈ L(v) for all v ∈ V. If G is acyclically L‐list colorable for any list assignment with |L (v)|≥ k for all v ∈ V, then G is acyclically k‐choosable. In this article, we prove that every planar graph G without 4‐ and 5‐cycles, or without 4‐ and 6‐cycles is acyclically 5‐choosable. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 245–260, 2007     

Acyclic 5‐choosability of planar graphs without adjacent short cycles

The conjecture on acyclic 5‐choosability of planar graphs [Borodin et al., 2002] as yet has been verified only for several restricted classes of graphs. None of these classes allows 4‐cycles. We prove that a planar graph is acyclically 5‐choosable if it does not contain an i‐cycle adjacent to a j‐cycle where 3?j?5 if i = 3 and 4?j?6 if i = 4. This result absorbs most of the previous work in this direction. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:169‐176, 2011     

Bipolar neutrosophic planar graphs

Fuzzy graph theory is used for solving real-world problems in different fields, including theoretical computer science, engineering, physics, combinatorics and medical sciences. In this paper, we present conepts of bipolar neutrosophic multigraphs, bipolar neutrosophic planar graphs, bipolar neutrosophic dual graphs, and study some of their related properties. We also describe applications of bipolar neutrosophic graphs in road network and electrical connections.     

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     

Precoloring extension for K4‐minor‐free graphs

Let G=(V, E) be a graph where every vertex v∈V is assigned a list of available colors L(v). We say that G is list colorable for a given list assignment if we can color every vertex using its list such that adjacent vertices get different colors. If L(v)={1, …, k} for all v∈V then a corresponding list coloring is nothing other than an ordinary k‐coloring of G. Assume that W?V is a subset of V such that G[W] is bipartite and each component of G[W] is precolored with two colors taken from a set of four. The minimum distance between the components of G[W] is denoted by d(W). We will show that if G is K₄‐minor‐free and d(W)≥7, then such a precoloring of W can be extended to a 4‐coloring of all of V. This result clarifies a question posed in 10. Moreover, we will show that such a precoloring is extendable to a list coloring of G for outerplanar graphs, provided that |L(v)|=4 for all v∈V\W and d(W)≥7. In both cases the bound for d(W) is best possible. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 284‐294, 2009     

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