Chromatic number for a path X_(n,m)(Path) is 2n+m+e . Here n is no. of distinct arcs while m is no. of distinct edges .

X_(n,m)(Path)= 2n+m+e , e=1 if m=0 or odd , e=2 if m!=0 and even .

For example , for (0,2) path chromatic number is 2*0 + 2 + 2 = 4 . It means that minimum 4 colors are needed to color vertices of the path such that no adjacent vertices is of same color .

My question is {What is minimum l for which there exists an (n,m) -path P on l vertices satisfying X_(n,m)(Path) = 2n+m+e .

Please provide any code for this , any idea of how to write the code or any reference code for this .

One thing to clear this is not straight forward shortest path problem and i have tried dijiksta .

To make it more understandable let us take (0,2) Path example , it has no arcs and 2 types of edges (blue and green ) .

X_(0,2)(path)=4 It means 4 minimum colors are required for coloring the vertices of the path

Our aim is to find shortest (0,2) -path having 4 colors .

Picture attached : Starting with blue color for vertex 1 , vertex 2 can’t be of blue color so it is of red color . Edge between v1 and v2 is orange . Now our aim is to minimize the color use , edge between v2 and v3 can’t be orange again , so it is black . Now we try to put blue color again on v3 but can’t be possible as pair of colors should have same type of edge , so if we put blue agin it will violate this rule , we can’t put red again , it is obvious . So vertex 3 is of green color . edge between vertex 3 and 4 can’t be black now so will be orange . Again we will aim to minimize color use , so try to put color blue on v4 . It seems perfect as no law is violated . So vertex 4 is of blue color , can’t be green and red ,same reason stated above . We can’t stop here as minimum 4 colors have to be used . Now edge between v4 and v5 can’t be orange so will be black . Now again try to minimize the color use . Let start with red , it is not possible as red and blue can’t have black edge between them , can’t be green for same reason . So new color yellow is given to v5 . Since 4 colors are used , so our shortest path will have 5 vertices(0,2)-path

I have to derive the same for (0,m) -paths and generate a sequence computationally till m=30 , and then prove it theorotically

Please provide pseudo code ideas or code refernces