Search

As an efficient theoretical tool, graph theory is widely used in computing chemistry. In terms of index computation on molecular graphs, the researchers can learn the potential properties of chemical compounds, including drugs, materials, and organics. In this paper, by means of distance computation, we study the eccentric version indices of cycloalkanes which occur quite frequently in the chemical drugs and other compounds. The promising prospects of the application for the physical, chemical, medical, and pharmacy engineering are illustrated by theoretical conclusions obtained in this article.

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):[email protected]?V}, there exists a proper acyclic coloring @p of G such that @p(v)@?L(v) for all [email protected]?V. If G is acyclically L-list colorable for any list assignment with |L(v)|>=k for all [email protected]?V, then G is acyclically k-choosable. In this paper we prove that every planar graph without 4-cycles and without two 3-cycles at distance less than 3 is acyclically 5-choosable. This improves a result in [M. Montassier, P. Ochem, A. Raspaud, On the acyclic choosability of graphs, J. Graph Theory 51 (2006) 281-300], which says that planar graphs of girth at least 5 are acyclically 5-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.