Search

A total k -coloring of a graph is an assignment of k colors to its vertices and edges such that no two adjacent or incident elements receive the same color. The total coloring conjecture (TCC) states that every simple graph G has a total Δ G + 2 -coloring, where Δ G is the maximum degree of G. This conjecture has been confirmed for planar graphs with maximum degree at least 7 or at most 5, i.e., the only open case of TCC is that of maximum degree 6. It is known that every planar graph G of Δ G ≥ 9 or Δ G ∈ 7,8 with some restrictions has a total Δ G + 1 -coloring. In particular, in (Shen and Wang, 2009), the authors proved that every planar graph with maximum degree 6 and without 4-cycles has a total 7-coloring. In this paper, we improve this result by showing that every diamond-free and house-free planar graph of maximum degree 6 is totally 7-colorable if every 6-vertex is not incident with two adjacent four cycles or three cycles of size p , q , ℓ for some p , q , ℓ ∈ 3,4,4 , 3,3,4 . [ABSTRACT FROM AUTHOR]

An acyclic coloring of a graph is a proper coloring of the graph, for which every cycle uses at least three colors. Let G 4 be the set of maximal planar graphs of minimum degree 4, such that each graph in G 4 contains exactly four odd-vertices and the subgraph induced by the four odd-vertices contains a quadrilateral. In this article, we show that every acyclic 4-coloring of a maximal planar graph with exact four odd-vertices is locally equitable with regard to its four odd-vertices. Moreover, we obtain a necessary and sufficient condition for a graph in G 4 to be acyclically 4-colorable, and give an enumeration of the acyclically 4-colorable graphs in G 4 . [ABSTRACT FROM AUTHOR]

It is known that Total Coloring Conjecture (TCC) was verified for planar graphs with maximum degree Δ ≠ 6 . In this paper, we prove that TCC holds for planar graphs G with Δ ( G ) = 6 , if G does not contain any subgraph isomorphic to a 4-fan. [ABSTRACT FROM AUTHOR]

A graphGis uniquelyk-colourable if the chromatic number ofGiskandGhas only onek-colouring up to permutation of the colours. Aksionov [On uniquely 3-colorable planar graphs, Discrete Math. 20 (1977), pp. 209–216] conjectured that every uniquely 3-colourable planar graph with at least four vertices has two adjacent triangles. However, in the same year, Melnikov and Steinberg [L.S. Mel'nikov and R. Steinberg,One counterexample for two conjectures on three coloring, Discrete Math. 20 (1977), pp. 203–206.] disproved the conjecture by constructing a counterexample. In this paper, we prove that if a uniquely 3-colourable planar graphGhas at most 4 triangles thenGhas two adjacent triangles. Furthermore, for any, we construct a uniquely 3-colourable planar graph withktriangles and without adjacent triangles. [ABSTRACT FROM PUBLISHER]

A graph G is uniquely k-colorable if the chromatic number of G is k and G has only one k -coloring up to permutation of the colors. A uniquely k -colorable graph G is edge-critical if G − e is not a uniquely k -colorable graph for any edge e ∈ E ( G ) . Mel’nikov and Steinberg (Mel’nikov and Steinberg, 1977) asked to find an exact upper bound for the number of edges in an edge-critical uniquely 3-colorable planar graph with n vertices. In this paper, we give some properties of edge-critical uniquely 3-colorable planar graphs and prove that if G is such a graph with n ( ≥ 6 ) vertices, then | E ( G ) | ≤ 5 2 n − 6 , which improves the upper bound 8 3 n − 17 3 given by Matsumoto (Matsumoto, 2013). Furthermore, we find some edge-critical uniquely 3-colorable planar graphs with n ( = 10 , 12 , 14 ) vertices and 5 2 n − 7 edges. [ABSTRACT FROM AUTHOR]

A set D ⊆ V ( G ) of a graph G is a dominating set if every vertex v ∈ V ( G ) is either in D or adjacent to a vertex in D . The domination number γ ( G ) of a graph G is the minimum cardinality of a dominating set of G . Campos and Wakabayashi (2013) and Tokunaga (2013) proved independently that if G is an n -vertex maximal outerplanar graph having t vertices of degree 2, then γ ( G ) ≤ n + t 4 . We improve their upper bound by showing γ ( G ) ≤ n + k 4 , where k is the number of pairs of consecutive 2-degree vertices with distance at least 3 on the outer cycle. Moreover, we prove that γ ( G ) ≤ 5 n 16 for a Hamiltonian maximal planar graph G with n ≥ 7 vertices. [ABSTRACT FROM AUTHOR]