$100$

Sandeep S$.$ Joshi and Kishor F$.$ Pawar

Theorem $3\mathrm{.}4.$ For the ring $Z_{p^4},$

$P{G}_1(Z_{p^4})=\frac{p^4-p^3+2p^2}{2},ifpis$ odd prime.

$=5=p+3,ifp=2.$

if $p$ is odd prime.

Proof. Any two non$-$zero elements of $P{G}_1(Z_{p^4})$ are adjacent if and only if both these elements are divisible by $p^2$ and $p^3.$ There are $p^2-1$ elements divisible by $p^2$ and $p^3$ and all are adjacent to each other. So$,$ these vertices induces a complete subgraph $k_{p^2-1}$ and the vertices of this clique can be colored with $p^2-1$ colors.

There are $p^2(p-1)$ elements which are divisible by $p$ but not $p^2$ and $p^3.$ These elements are not adjacent to each other but are adjacent to the elements divisible by $p^3$ and the elements in a set of units. So$,$ the vertices divisible by $p$ can be colored with any one color assigned to the vertices divisible by $p^2.$

The remaining $p^3(p-1)$ elements which are not divisible by $p,p^2$ and $p^3$ are adjacent to all the elements in a set of non$-$zero zero divisors and form two complete subgraphs having $\frac{p^3(p-1)}{2}$ elements in each subgraph. So$,$ the vertices in these two complete subgraphs can be properly colored with $\frac{p^3(p-1)}{2}$ colors except the colors assigned to the vertices of the clique $k_{p^2-1}.$

Also, the vertex $0$ is adjacent to all other vertices in $P{G}_1(Z_{p^4}).$ So$,$ the vertex $0$ can be colored with a single color except the colors assigned to the vertices of the cliques cliques $k_{p^2-1},k_{\frac{p^3(p-1)}{2}}.$ Thus, the graph $P{G}_1(Z_{p^4})$ can be properly colored with $(p^2-1)+\frac{p^3(p-1)}{2}+1$ colors. Therefore, $P{G}_1(Z_{p^4})=\frac{p^4-p^3+2p^2}{2},$ if $p$ is an odd prime.

In case when $p=2,Z_{16}=\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15\}.$ Here, the elements $\{0,4,8,12\}$ forms a complete subgraph $k_4$ and the vertices of this clique can be colored with $4$ colors. The elements $\{2,6,10,14\}$ are not adjacent to each other and the elements $4$ and $12.$ So$,$ these vertices can be colored with any one color assigned to the vertices $4$ and $12.$ The elements $\{1,3,5,7,9,11,13,15\}$ are not adjacent to each other but are adjacent to all the elements in a set $\{0,2,4,6,8,10,12,14\}.$ So$,$ these vertices can be colored with a single color except the colors assigned to the vertices of the clique $k_4.$ Thus, the graph $P{G}_1(Z_{16})$ can be properly colored by $5$ colors. Hence $P{G}_1(Z_{16})=5=p+3.$

Problem: elements divisible by p $\{2,6,10,14\}$ should be adjacent to elements divisible by p$^3\{8\},$ from the code below elements divisible by p and elements divisible by p$^3$ are not adjacent to each other $,$ please correct the code, namely the def is$\_$adjacent part

code :

import networkx as nx

import matplotlib.pyplot as plt

def is$\_$adjacent$\_$zp$4($v$,$ u$,$ p$)$:

if v $==$ u:

return False # No self$-$loops

if v $==0$ or u $==0$:

return True # Vertex $0$ is adjacent to all other vertices

if v $\%($p$*$p$)==0$ and u $\%($p$*$p$)==0$:

return True # divisible by p$^2$

if v $\%($p$*$p$*$p$)==0$ and u $\%($p$*$p$*$p$)==0$:

return True # divisible by p$^3$

if v $\%$ p $==0$ and u $\%$ p $==0$:

return False

#if $($v $\%$ p $==0$ and v $\%($p$**3)==0)$ and $($u $\%$ p $==0$ and u $\%($p$**3)==0)$:

#return True

if $($v $\%$ p $==0$ and v $\%($p$**3)!=0)$ and $($u $\%$ p $==0$ and u $\%($p$**3)!=0)$:

return True

if $($v $\%$ p $==0$ and v $\%($p$**2)!=0$ and u $\%$ p $==0$ and u $\%($p$**2)!=0)$:

return True

# Kondisi adjacency jika tidak habis dibagi p$,$ p$^2,$ atau p$^3$

if $($v $\%$ p $!=0$ and v $\%($p$**2)!=0$ and v $\%($p$**3)!=0)$ and $($u $\%$ p $!=0$ and u $\%($p$**2)!=0$ and u $\%($p$**3)!=0)$:

return $($v$+$u$)\%$ p $!=0$

return True

def generate$\_$graph$($vertices$,$ p$,$ is$\_$adjacent$)$:

edges $=[($v$,$ u$)$ for v in vertices for u in vertices if is$\_$adjacent$($v$,$ u$,$ p$)]$

# Create the graph

G $=$ nx$.$Graph$()$

G$.$add$\_$nodes$\_$from$($vertices$)$

G$.$add$\_$edges$\_$from$($edges$)$

return G

def analyze$\_$graph$($G$)$:

max$\_$clique $=$ max$($nx$.$find$\_$cliques$($G$),$ key$=$len$)$

max$\_$clique$\_$size $=$ len$($max$\_$clique$)$

color$\_$map $=$ nx$.$coloring.greedy$\_$color$($G$,$ strategy$=$"largest$\_$first"$)$

chromatic$\_$number $=$ max$($color$\_$map.values$())+1$

#coloring$[0]=$ unique$\_$color

return chromatic$\_$number, max$\_$clique, max$\_$clique$\_$size

def draw$\_$graph$($G$,$ color$\_$map, title$)$:

plt$.$figure$($figsize$=(8,6))$

pos $=$ nx$.$spring$\_$layout$($G$)$ # Layout adjusted for better visualization

node$\_$colors $=[$color$\_$map$[$node$]$ for node in G$.$nodes$()]$

nx$.$draw$\_$networkx$\_$nodes$($G$,$ pos, node$\_$color$=$node$\_$colors, node$\_$size$=300,$ cmap$=$plt$.$cm$.$rainbow$)$

nx$.$draw$\_$networkx$\_$edges$($G$,$ pos, width$=1\mathrm{.}0,$ alpha$=0\mathrm{.}5)$

nx$.$draw$\_$networkx$\_$labels$($G$,$ pos, labels$=\{$node: str$($node$)$ for node in G$.$nodes$()\},$ font$\_$color$=$'black', font$\_$size$=10,$ font$\_$weight$=$'medium'$)$

plt$.$title$($title$)$

plt$.$axis$(\text{'}$off$\text{'})$

plt$.$show$()$

def find$\_$adjacencies$($vertices$,$ p$,$ is$\_$adjacent$)$:

adjacent$\_$pairs $=[]$

non$\_$adjacent$\_$pairs $=[]$

for v in vertices:

for u in vertices:

if v $<$ u:

if is$\_$adjacent$($v$,$ u$,$ p$)$:

adjacent$\_$pairs.append$(($v$,$ u$))$

else:

non$\_$adjacent$\_$pairs.append$(($v$,$ u$))$

return adjacent$\_$pairs, non$\_$adjacent$\_$pairs

# Example usage for p$=2$

p $=2$

vertices$\_$zp$4=$ list$($range$($p $*$ p $*$ p $*$ p$))$

# Generate graph for Z$16$

G$\_$zp$4=$ generate$\_$graph$($vertices$\_$zp$4,$ p$,$ is$\_$adjacent$\_$zp$4)$

# Analyze the graph

chromatic$\_$number$\_$zp$4,$ max$\_$clique$\_$zp$4,$ max$\_$clique$\_$size$\_$zp$4=$ analyze$\_$graph$($G$\_$zp$4)$

# Expected chromatic number

expected$\_$chromatic$\_$number$\_$zp$4=$ p $+3$

print$($f$"$Expected chromatic number Zp$4$: $\{$expected$\_$chromatic$\_$number$\_$