Graph theory is an important area of Applied Mathematics with a broad spectrum of applications in many fields. In the Call for Papers for this issue, I asked for submissions presenting new and inoovative approaches for traditional graph-theoretic problems as well as for new applications of graph theory in emerging fields, such as network security, computer science and data analysis, bioinformatics, operations research, engineering and manufacturing, physics and chemistry, linguistics, or social sciences.
In response to the Call for Papers, we had an enormous resonance, and altogether 151 submissions have been received among which finally 20 papers have been accepted for this special issue, all of which are of high quality, reflecting the great interest in the area of Graph Theory. This corresponds to an acceptance rate of 13.2%. The authors of these accepted publications come from 13 different countries: USA, China, Pakistan, India, Iran, Marocco, Slovenia, United Arab Emirates, Oman, Spain, Mexico, Serbia, and Belarus, where most authors are from the first two countries. All submissions have been reviewed, as a rule, by at least three experts in the field of Graph Theory. Subsequently, all published papers in this special issue are briefly surveyed in increasing order of their publication dates. We hope that the readers will find interesting theoretical ideas in this special issue and that researchers will find new inspirations for future works. Since also for my previous special issue ‘Discrete Optimization: Theory, Algorithms, and Applications’a lot of graph-theoretic works have been submitted, I would like to remind the readership on the follow-up issue’Novel Approaches for Discrete Optimization Problems’ with a submission deadline of May 31, 2020, where also works related to graphs and networks are mentioned in the Call for Papers. The first accepted paper by Tilley [1] is related to the 4-color theorem which has been proven by showing that a minimal counterexample does not exist. Here the author proves that a minimum counterexample must also satisfy a particular coloring property which he denotes as Kempe–Locking. However, the main intention of this paper is not an alternative proof of the 4-color theorem but an exploratory paper aimed at gaining a deeper understanding of why the 4-color theorem is true and a new approach to understand why planar graphs are 4-colorable by investigating whether the connectivity and coloring properties are compatible. Zhang et al.[2] consider so-called generalized hypergraphs H denoted as r-uniform if all the hyperedges have the same cardinality r. Such a graph is called a generalized hypertree GHT, if after removing any hyperedge E, GHT− E has exactly k components with 2≤ k≤ r. Focusing first on the case k= 2, they determine bounds on the number of edges. In particular, the authors show that an r-uniform generalized GHT on n vertices has at least 2n/(r+ 1) edges and at most n− r+ 1 edges if r≥ 3, n≥ 3 and that the lower and upper bounds on the edge number are tight. Finally, the case of a fixed value k≤ r− 1 is also discussed.