{2, 2}-EXTENDABILITY OF PLANAR GRAPHS
Article Sidebar
Main Article Content
Abstract
In this paper, the idea of assigning lists of varying sizes to vertices of a planar graph will be explored. Thomassen’s 5-list-coloring theorem states that plane graphs are list-colorable when two adjacent vertices on the boundary of the unbounded face are pre-colored, other vertices on the boundary of the unbounded face are assigned lists of size 3, and all other vertices of the graph are assigned lists of size 5. This can be thought of as being 2-extendable. Thomassen’s also defined an analogous property of 3-extendability, and later Definition, which corresponds to having the vertices of a 3-path along the boundary of the unbounded face pre-colored. While every planar graph is 2-extendable, it is not the case that every planar graph is 3-extendable.
Keywords: {i, j}-extendibility, {2, 2, 2}-extendable, 3-cycle.
Downloads
Article Details
Open Access: This is an open-access journal. All articles published in the Journal of Global Research in Mathematical Archives(JGRMA) are made immediately and permanently available under the Creative Commons Attribution 4.0 International (CC BY 4.0) License. Authors retain the copyright of their work and grant Journal of Global Research in Mathematical Archives(JGRMA) the right of first publication. This license permits unrestricted use, distribution, adaptation, and reproduction in any medium or format, including commercial use, provided the original author(s), source, and license are properly acknowledged.
Google Scholar Indexed | DOI Enabled | OAI-PMH Compliant | Open Access Journal
References
Dimitris Achlioptas and Cristopher Moore. Almost all graphs with average degree 4 are3-colorable. J. Comput. System Sci., 67(2):441{471, 2003. Special issue on STOC2002(Montreal, QC).
Michael O. Albertson. You can't paint yourself into a corner. J. Combin. Theory Ser. B,73(2):189{194, 1998.
Michael O. Albertson, Alexandr V. Kostochka, and Douglas B. West. Precoloring extensionsof Brooks' theorem. SIAM J. Discrete Math., 18(3):542{553, 2004/05.
Noga Alon. Restricted colorings of graphs. In Surveys in combinatorics, 1993 (Keele),volume 187 of London Math. Soc. Lecture Note Ser., pages 1{33. Cambridge Univ. Press,Cambridge, 1993.
Noga Alon. Degrees and choice numbers. Random Structures Algorithms, 16(4):364-368,2000.
Kenneth Appel and Wolfgang Haken. Every planar map is four colorable. Bull. Amer. Math. Soc., 82(5):711-712, 1976.