On the P 3 -Coloring of Bipartite Graphs

Zemiao Dai, Muhammad Naeem (), Zainab Shafaqat, Manzoor Ahmad Zahid and Shahid Qaisar
Additional contact information
Zemiao Dai: College of Information Technology, Anhui Vocational College of Defense Technology, Luan 237011, China
Muhammad Naeem: Department of Mathematics, COMSATS University Islamabad, Sahiwal 57000, Pakistan
Zainab Shafaqat: Department of Mathematics, COMSATS University Islamabad, Sahiwal 57000, Pakistan
Manzoor Ahmad Zahid: Department of Mathematics, COMSATS University Islamabad, Sahiwal 57000, Pakistan
Shahid Qaisar: Department of Mathematics, COMSATS University Islamabad, Sahiwal 57000, Pakistan

Mathematics, 2023, vol. 11, issue 16, 1-15

Abstract: The advancement in coloring schemes of graphs is expanding over time to solve emerging problems. Recently, a new form of coloring, namely P 3 -coloring, was introduced. A simple graph is called a P 3 -colorable graph if its vertices can be colored so that all the vertices in each P 3 path of the graph have different colors; this is called the P 3 -coloring of the graph. The minimum number of colors required to form a P 3 -coloring of a graph is called the P 3 -chromatic number of the graph. The aim of this article is to determine the P 3 -chromatic number of different well-known classes of bipartite graphs such as complete bipartite graphs, tree graphs, grid graphs, and some special types of bipartite graphs. Moreover, we have also presented some algorithms to produce a P 3 -coloring of these classes with a minimum number of colors required.

Keywords: graph coloring; chromatic number; P 3 -coloring; P 3 -chromatic number; bipartite graphs (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/16/3487/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/16/3487/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:16:p:3487-:d:1215755

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().