文章基本信息

标题：Recursive Linear Bounds for the Vertex Chromatic Number of the Pancake Graph
本地全文：下载
作者：Aldrich Ellis C. Asuncion ; Renzo Roel P. Tan ; Christian Paul O. Chan Shio 等
期刊名称：Lecture Notes in Engineering and Computer Science
印刷版ISSN：2078-0958
电子版ISSN：2078-0966
出版年度：2022
卷号：52
期号：1
语种：English
出版社：Newswood and International Association of Engineers
摘要：The pancake graph has been the subject of re?search. While studies on the various aspects of the graphare abundant, results on the chromatic properties may befurther enhanced. Revolving around such context, the paperadvances an alternative method to produce novel linear boundsfor the vertex chromatic number of the pancake graph. Theaccompanying demonstration takes advantage of symmetriesinherent to the graph, capturing the prefix reversal of sub?sequences through a homomorphism. Contained within theargument is the incorporation of known vertex chromaticnumbers for certain orders of pancake graphs, rendering tighterbounds possible upon the release of new findings. In closing, acomparison with existing bounds is done to establish the relativeadvantage of the proposed technique.
关键词：chromatic number; linear bound; pancake graph; vertex coloring.