Consider n disjoint triangles and a cycle on the 3n vertices of the n triangles. In 1986, Du, Hsu, and Hwang conjectured that the union of the n triangles and the cycle has independent number n. Soon later, Paul Erdös improved it to a stronger version that every cycle-plus-triangle graph is 3-colorable. This conjecture was proven by H. Fleischner and M. Stiebitz. In this note, we want to give an extension of the above conjecture with an application in switching networks.
Du, Ding-Zhu; Ngo, Hung Q..
An Extension of DHH-Erdös Conjecture on Cycle-Plus-Triangle Graphs with Application in Switching Networks.
Retrieved from the University of Minnesota Digital Conservancy,
Content distributed via the University of Minnesota's Digital Conservancy may be subject to additional license and use restrictions applied by the depositor.