Search

Recently, Kowalik, Sereni, and Škrekovski proved that planar graphs with maximum degree 9 are 10-totally colorable. This work proves that planar graphs with maximum degree 8 and without intersecting triangles are 9-totally colorable.

Let G be a graph embedded in a surface of characteristic zero with maximum degree @D. The edge-face chromatic number @g"e"f(G) of G is the least number of colors such that any two adjacent edges, adjacent faces, incident edge and face have different colors. In this paper, we prove that @g"e"f(G)@[email protected]+1 if @D>=13, @g"e"f(G)@[email protected]+2 if @D>=12, @g"e"f(G)@[email protected]+3 if @D>=4, and @g"e"f(G)@?7 if @[email protected]?3.

The (2,1)-total labelling number λ2T(G) of a graph G is the width of the smallest range of integers that suffices to label the vertices and the edges of G such that no two adjacent vertices have the same label, no two adjacent edges have the same label and the difference between the labels of a vertex and its incident edges is at least 2. In this paper we prove that if G is an outerplanar graph with maximum degree Δ(G), then λ2T(G)⩽Δ(G)+2 if Δ(G)⩾5, or Δ(G)=3 and G is 2-connected, or Δ(G)=4 and G contains no intersecting triangles.

An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that any pair of adjacent vertices have different sets of colors. The minimum number of colors needed for such a total coloring of G is denoted by ? a ? ( G ) . In this note, we show that ? a ? ( G ) ? 2 Δ for any graph G with maximum degree Δ ? 3 .

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 lc ( G ) 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) lc ( G ) ? 1 2 ( Δ ( G ) 2 + Δ ( G ) ) ; (2) lc ( G ) ? 8 if Δ ( G ) ? 4 ; (3) lc ( G ) ? 14 if Δ ( G ) ? 5 ; (4) lc ( G ) ? ? 0.9 Δ ( G ) ? + 5 if G is planar and Δ ( G ) ? 52 .

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 Δ .