Javascript must be enabled to continue!
On the P3 Coloring of Graphs
View through CrossRef
The vertex coloring of graphs is a well-known coloring of graphs. In this coloring, all of the vertices are assigned colors in such a way that no two adjacent vertices have the same color. We can call this type of coloring P2 coloring, where P2 is a path graph. However, there are situations in which this type of coloring cannot give us the solution to the problem at hand. To answer such questions, in this article, we introduce a novel graph coloring called P3 coloring. A graph is called P3-colorable if we can assign colors to the vertices of the graph such that the vertices of every P3 path are distinct. The minimum number of colors required for a graph to have P3 coloring is called the P3 chromatic number. The aim of this article is, in general, to prove some basic results concerning this coloring, and, in particular, to compute the P3 chromatic number for different symmetric families of graphs.
Title: On the P3 Coloring of Graphs
Description:
The vertex coloring of graphs is a well-known coloring of graphs.
In this coloring, all of the vertices are assigned colors in such a way that no two adjacent vertices have the same color.
We can call this type of coloring P2 coloring, where P2 is a path graph.
However, there are situations in which this type of coloring cannot give us the solution to the problem at hand.
To answer such questions, in this article, we introduce a novel graph coloring called P3 coloring.
A graph is called P3-colorable if we can assign colors to the vertices of the graph such that the vertices of every P3 path are distinct.
The minimum number of colors required for a graph to have P3 coloring is called the P3 chromatic number.
The aim of this article is, in general, to prove some basic results concerning this coloring, and, in particular, to compute the P3 chromatic number for different symmetric families of graphs.
Related Results
Graphs with at most two moplexes
Graphs with at most two moplexes
AbstractA moplex is a natural graph structure that arises when lifting Dirac's classical theorem from chordal graphs to general graphs. The notion is known to be closely related to...
Weakly Modular Graphs and Nonpositive Curvature
Weakly Modular Graphs and Nonpositive Curvature
This article investigates structural, geometrical, and topological characterizations and properties of weakly modular graphs and of cell complexes derived from them. The unifying t...
Efficient Open Dominator Coloring in Cycles and Paths
Efficient Open Dominator Coloring in Cycles and Paths
In 2006, Gera introduced and studied the dominator chromatic number. [4]. A dominator coloring of a graph G is a proper coloring in which each vertex of G dominates all the vertice...
Graph Coloring
Graph Coloring
In this chapter a particular type of graph labeling, called graph coloring, is introduced and discussed. In the first part, the simple type of coloring, vertex coloring, is focused...
On the total and conformable colorings of line regular graphs
On the total and conformable colorings of line regular graphs
A conformable coloring of a $k$-regular graph $G=(V,E)$ is a $(k+1)$-vertex coloring in which every color class (including empty ones) has cardinality the same parity as $|V|$; su...
Independent Set in Neutrosophic Graphs
Independent Set in Neutrosophic Graphs
New setting is introduced to study neutrosophic independent number and independent neutrosophic-number arising neighborhood of different vertices. Neighbor is a key term to have th...
Failed Independent Number in Neutrosophic Graphs
Failed Independent Number in Neutrosophic Graphs
New setting is introduced to study neutrosophic failed-independent number and failed independent neutrosophic-number arising neighborhood of different vertices. Neighbor is a key t...
Computing a Minimum Subset Feedback Vertex Set on Chordal Graphs Parameterized by Leafage
Computing a Minimum Subset Feedback Vertex Set on Chordal Graphs Parameterized by Leafage
Abstract
Chordal graphs are characterized as the intersection graphs of subtrees in a tree and such a representation is known as the tree model. Restricting the characteriz...

