Incident Vertex \(\pi\)-Coloring of Graphs
DOI:
https://doi.org/10.26713/cma.v14i2.2215Keywords:
π coloring of graphs, Incident vertex π coloring, Fan graphs, Friendship graphs, Wheel graphs, Diamond graphs, Star and Double Star graphsAbstract
We defined the concept of \(\pi\)-coloring of graphs and incident vertex \(\pi\) coloring of graphs. The incident vertex \(\pi\) coloring number \((IV \pi CN)\) of graphs is different from all existing coloring techniques. The \(IV \pi CN\) of complete graph \((K_n)\) is \(n\). \(IV \pi CN\) of wheel, star, double star graph are \((n+1)\). Also, \(IV \pi CN\) of friendship, diamond and fan graphs are \(\Delta+1\). The \(IV \pi CN\) of double fan graph is \(\Delta+2\). The \(IV \pi CN\) of complete bipartite graphs \(K_{m,n}\) is \((m+n)\). The \(IV \pi CN\) of bipartite graph is bounded. Moreover, some results associated to enumeration of the number of graphs having equal incident vertex \(\pi\) chromatic number of few families are proved.
Downloads
References
K. Appel and W. Haken, Every planar map is four colorable – Part I: Discharging, Illinois Journal of Mathematics 21(3) (1977), 429 – 490, DOI: 10.1215/ijm/1256049011.
K. Appel and W. Haken, The solution of the four-color-map problem, Scientific American 237(4) (1977), 108 – 121, URL: http://www.jstor.org/stable/24953967.
K. Appel, W. Haken and J. Koch, Every planar map is four colorable – Part II: Reducibility, Illinois Journal of Mathematics 21(3) (1977), 491 – 567, DOI: 10.1215/ijm/1256049012.
M. Behzad, Graphs and Their Chromatic Numbers, Doctoral Thesis, Michigan State University, East Lansing, MI, USA, iv + 62 pages (1965), DOI: 10.25335/M5H41K22C.
S. Benzer, Fine structure of a genetic region in bacteriophage, Proceedings of the National Academy of Sciences (PNAS) 41(6) (1955), 344 – 354, DOI: 10.1073/pnas.41.6.344.
A. A. Bhange and H. R. Bhapkar, Perfect colouring of the graph with its kinds, Journal of Physics:Conference Series 1663 (2020), 012024, DOI: 10.1088/1742-6596/1663/1/012024.
H. R. Bhapkar and J. N. Salunke, Proof of four color map theorem by using PRN of graph, The Bulletin of Society for Mathematical Services and Standards 11 (2014), 26 – 30, DOI: 10.18052/www.scipress.com/BSMaSS.11.26.
G. D. Birkhoff, A determinant formula for the number of ways of coloring a map, Annals of Mathematics 14(1/4) (1912-1913), 42 – 46, DOI: 10.2307/1967597.
J. A. Bondy and U. S. R. Murthy, Graph Theory with Applications, North-Holland, 264 pages (1976).
N. Deo, Graph Theory with Applications to Engineering & Computer Science, Dover Publications, Inc., Mineola, New York (1974).
I. G. Dmitriev, Characterization of a class of k-trees, American Mathematical Society Translations: Series 2 132 (1986), 1 – 8, DOI: 10.1090/trans2/132.
L. Euler, Solutio problematis ad geometriam situs pertinentis, Commentarii Academiae Scientiarum Petropolitanae 8 (1741), 128 – 140, URL: https://scholarlycommons.pacific.edu/euler-works/53/, (English translation: L. Euler, Leonhard Euler and the Koenigsberg bridges, Scientific American 189 (1953), 66 – 70, DOI: 10.1038/scientificamerican0753-66).
C. F. Gauss, Demonstratio nova altera theorematis omnem functionem algebraicam rationalem integram unius veriabilis in factores reales primi vel secundi gradus resolvi posse, Commentationes Societatis Regiae Scientiarum Gottingensis Recentiores. Comm. Class. Math. 3 (1816), 107 – 142, URL: https://gdz.sub.uni-goettingen.de/id/PPN35283028X_0003_2NS?tify=%7B%22pages%22% 3A%5B268%2C269%5D%2C%22view%22%3A%22info%22%7D.
A. Hajnal and J. Surányi, Über die Auflösung von Graphen in vollständige Teilgraphen, Annales Universitatis Scientiarium Budapestinensis de Rolando Eötvös Nominatae Sectio Mathematica 1 (1958), 113 – 121, URL: http://annalesm.elte.hu/annales01-1958/Annales_1958_T-I.pdf.
F. Harary, Graph Theory, Addison-Wesley Publishing Company, Reading, Massachusetts (1969).
P. J. Heawood, Map-colour theorems, The Quarterly Journal of Pure and Applied Mathematics 24 (1890), 332 – 338, URL: https://babel.hathitrust.org/cgi/pt?id=inu.30000050138159&+seq=344&seq=9.
S. Hong, J. H. Kwah, K. H. Kim and F. W. Roush (editors), Combinatorial and Computational Mathematics, World Scientific Publications Company, Singapore, 288 pages (2001), DOI: 10.1142/4749.
A. B. Kempe, On the geographical problem of the four colours, American Journal of Mathematics 2(3) (1879), 193 – 200, DOI: 10.2307/2369235.
M. Kubale (editor), Graph Colorings, Contemporary Mathematics, Vol. 352, American Mathematical Society, (2004), DOI: 10.1090/conm/352.
O. Ore and J. Stemple, Numerical calculations on the four-color problem, Journal of Combinatorial Theory 8(1) (1970), 65 – 78, DOI: 10.1016/S0021-9800(70)80009-6.
D. S. Riheson, Euler’s Gem: The Polyhedron Formula and the Birth of Topology, Princeton University Press, 336 pages (2008), URL: https://www.jstor.org/stable/j.ctt7sqb7.
N. Robertson, D. Sanders, P. Seymour and R. Thomas, The four-colour theorem, Journal of Combinatorial Theory, Series B 70(1) (1997), 2 – 44, DOI: 10.1006/jctb.1997.1750.
G.-C. Rota, On the foundations of combinatorial theory I – theory of Möbius functions, Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 2 (1964), 340 – 368, DOI: 10.1007/BF00531932.
J. P. Tremblay and R. Manohar, Discrete Mathematical Structures with Applications to Computer Science, 1st edition, McGraw Hill Education, 622 pages (2017).
D. B. West, Introduction to Graph Theory, 2nd edition, Pearson Education, Inc., 470 pages (2000).
H. Whitney, The coloring of graphs, Annals of Mathematics (Second Series) 33(4) (1932), 688 – 718, DOI: 10.2307/1968214.
R. J. Wilson, Introduction to Graph Theory, 5th edition, Pearson Education Limited, 192 pages (2010).
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a CCAL that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
