Research ArticleOpen AccessGoogle Scholar indexed
Remarks on Extremal Overfull Graphs
Department of Mathematics, Faculty of Science, Shahid Rajaee Teacher Training University, Tehran, Iran
- 1 Department of Mathematics, Faculty of Science, Shahid Rajaee Teacher Training University, Tehran, Iran
Applied Mathematics·Volume 04 (2013)·Pages 1106–1108·Published 23 July 2013·DOI10.4236/am.2013.48149
Copy link · social · email
Abstract
An overfull graph is a graph whose number of its edges is greater than the product of its maximum degree and [ n /2] , where n is the number of vertices. In this paper, some extremals of overfull graphs are presented. We also classify all plannar overfull graphs.
KeywordsOverfull GraphEdge Chromatic NumberPlannar Graph
- G. Chartrand and F. Zhang, “Chromatic Graph Theory,” Chapman and Hall/CRC, London, 2008. doi:10.1201/9781584888017
- A. G. Chetwynd and A. J. W. Hilton, “Star Multigraphs with Three Vertices of Maximum Degree,” Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 100, No. 2, 1986, pp. 303-317. doi:10.1017/S030500410006610X
- T. Niessen, “How to Find Overfull Subgraphs in Graphs with Large Maximum Degree,” Discrete Applied Mathe matics, Vol. 51, No. 1-2, 1994, pp. 117-125.
- M. Plantholt, “Overfull Conjecture for Graphs with High Minimum Degree,” Journal of Graph Theory, Vol. 47, No. 2, 2004, pp. 73-80. doi:10.1002/jgt.20013