Search

An embedded graph G = ( V , E , F ) on the torus is entirely k-colorable if V ∪ E ∪ F can be colored with k colors such that any two adjacent or incident elements receive different colors. In this paper, we prove that every embedded graph G on the torus with maximum degree Δ ≥ 10 is entirely ( Δ + 2 ) -colorable.

A proper edge coloring is called acyclic if no bichromatic cycles are produced. It was conjectured that every simple graph G with maximum degree $$\varDelta $$ is acyclically edge- $$(\varDelta +2)$$ -colorable. Basavaraju and Chandran (J Graph Theory 61:192–209, 2009) confirmed the conjecture for non-regular graphs G with $$\varDelta =4$$ . In this paper, we extend this result by showing that every 4-regular graph G without 3-cycles is acyclically edge-6-colorable.

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 integer k such that G has an acyclic edge coloring using k colors. Fiamcik (1978) and later Alon, Sudakov and Zaks (2001) conjectured that a^'(G)@[email protected]+2 for any simple graph G with maximum degree @D. In this paper, we show that if G is a planar graph without a 3-cycle adjacent to a 4-cycle, then a^'(G)@[email protected]+2, i.e., this conjecture holds.

A proper edge coloring of a graph G without isolated edges is neighbor-distinguishing if any two adjacent vertices have distinct sets consisting of colors of their incident edges. The neighbor-distinguishing index of G is the minimum number ndi(G) of colors in a neighbor-distinguishing edge coloring of G. Zhang, Liu, and Wang in 2002 conjectured that if G is a connected graph of order at least 6. In this article, the conjecture is verified for planar graphs with maximum degree at least 12.

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.

A proper coloring of the vertices of a graph G is called a star-coloring if the union of every two color classes induces a star forest. The graph G is L-star-colorable if for a given list assignment L there is a star-coloring ? such that ?(v)?L(v). If G is L-star-colorable for any list assignment L with |L(v)|?k for all v?V(G), then G is called k-star-choosable. The star list chromatic number of G, denoted by $\chi_{s}^{l}(G)$ , is the smallest integer k such that G is k-star-choosable. In this paper, we prove that every planar subcubic graph is 6-star-choosable.

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 473 2004, 140-153.

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 integer k such that G has an acyclic edge coloring using k colors. Fiamcik (1978) [9] and later Alon et al. (2001) [2] conjectured that a^'(G)@?@D+2 for any simple graph G with maximum degree @D. In this paper, we confirm this conjecture for planar graphs without 5-cycles.

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 integer k such that G has an acyclic edge coloring using k colors. Fiamcik (Math. Slovaca 28:139–145, 1978) and later Alon, Sudakov and Zaks (J. Graph Theory 37:157–167, 2001) conjectured that a′(G)≤Δ+2 for any simple graph G with maximum degree Δ. In this paper, we confirm this conjecture for planar graphs G with Δ≠4 and without 4-cycles.

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 integer k such that G has an acyclic edge coloring using k colors. In this paper, we determine completely the acyclic chromatic indices of K 4-minor free graphs with maximum degree not equal to 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 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 @D has a^'(G)[email protected] if there exists a pair (k,m)@?{(3,11),(4,8),(5,7),(8,6)} such that G satisfies @D>=k and g(G)>=m.

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 integer 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)?5 and maximum degree Δ?12 has a?(G)=Δ.

A short cycle means a cycle of length at most 7. In this paper, we prove that planar graphs without adjacent short cycles are 3-colorable. This improves a result of Borodin et al. (2005).

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 numberlc(G) 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 @D has lc(G)=@?@D2@?+1 if G satisfies one of the following four conditions: (1) g>=13 and @D>=3; (2) g>=11 and @D>=5; (3) g>=9 and @D>=7; (4) g>=7 and @D>=13. Moreover, we give better upper bounds of linear chromatic number for planar graphs with girth 5 or 6.

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 lc(G) of the graph G is the smallest number of colors in a linear coloring of G.

The 2-distance vertex-distinguishing index $$\chi '_{d2}G$$i¾?d2'G of a graph G is the least number of colors required for a proper edge coloring of G such that any pair of vertices at distance 2 have distinct sets of colors on their incident edges. Let G be a bipartite outerplanar graph of order n with maximum degree $$\varDelta $$Δ. We give an algorithm of time complexity $$On^3$$On3 to show that $$\chi '_{d2}G \le \varDelta +2$$i¾?d2'G≤Δ+2.

A plane graph G is said to be k-edge-face choosable if, for every list L of colors satisfying |L(x)|=k for every edge and face x, there exists a coloring which assigns to each edge and each face a color from its list so that any adjacent or incident elements receive different colors. We prove that every plane graph G with maximum degree Δ (G) is (Δ (G)+3)-edge-face choosable.

A graph G is called (k, d)*-choosable if, for every list assignment L satisfying |L(v)| = k for all v ϵ V(G), there is an L-coloring of G such that each vertex of G has at most d neighbors colored with the same color as itself. In this note, we prove that every planar graph without 4-cycles and l-cycles for some l ϵ {5, 6, 7} is (3, 1)*-choosable.

Graph coloring is an important branch in graph theory, since it has come from the famous Four-Color Problem and is of many applications in time tabling, sequencing, scheduling, coding, frequency channel assignment, and other practical problems. Since this area includes quite a number of subjects and there exist too many interesting problems, only several interested subjects are selected in this chapter. An introduction of concepts and symbols on graph coloring is given in Sect. 1. Section 2 is devoted to discussing the classical vertex-coloring problem, involving the general upper bound of the vertex chromatic number, and the colorability and choosability of planar graphs and graphs embeddable in a surface. Section 3 investigates the acyclic vertex coloring and acyclic edge coloring of graphs as well their as various generalizations such as star coloring, linear coloring, and acyclic improper coloring. Section 4 focus on some recent progresses on vertex-distinguishing edge-weighting problems. Two types of edge-weighting, that is, proper edge-weighting and non-proper edge-weighting, are mentioned respectively. The L.p; q/-labeling problem of graphs will be finally investigated in Sect. 5, including the L.2; 1/-labeling, the coloring of the square of a graph, the injective coloring, the backbone coloring, and the .d; 1/-total labeling. In each section, a somewhat detailed survey on the recent advance of the related direction and some open problems are provided.

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 integer $k$ such that $G$ has an acyclic edge coloring using $k$ colors. It was conjectured that $a'(G)\le \Delta+2$ for any simple graph $G$ with maximum degree $\Delta$. In this paper, we prove that if $G$ is a planar graph, then $a'(G)\leq\Delta +7$. This improves a result by Basavaraju et al. [{\em Acyclic edge-coloring of planar graphs}, SIAM J. Discrete Math., 25 (2011), pp. 463-478], which says that every planar graph $G$ satisfies $a'(G)\leq\Delta +12$., Comment: 23 pages, 1 figures

Graphs and Algorithms, A proper vertex coloring of a graphGis called a star-coloring if there is no path on four vertices assigned to two colors. The graph G is L-star-colorable if for a given list assignment L there is a star-coloring c such that c(v) epsilon L(v). If G is L-star-colorable for any list assignment L with vertical bar L(v)vertical bar \textgreater= k for all v epsilon V(G), then G is called k-star-choosable. The star list chromatic number of G, denoted by X-s(l)(G), is the smallest integer k such that G is k-star-choosable. In this article, we prove that every graph G with maximum average degree less than 3 is 8-star-choosable. This extends a result that planar graphs of girth at least 6 are 8-star-choosable [A. Kundgen, C. Timmons, Star coloring planar graphs from small lists, J. Graph Theory, 63(4): 324-337, 2010].

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 c of G such that c(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.

An acyclic list edge coloring of a graph G is a proper list edge coloring such that no bichromatic cycles are produced. In this paper, we prove that an outerplanar graph G with maximum degree Δ ≥ 5 has the acyclic list edge chromatic number equal to Δ .