On coloring of fractional powers of graphs

arXiv1212.3898MaRDI QIDQ6238080FDOQ6238080

Authors: Stephen G. Hartke, Hong Liu, Šárka Petříčková 

Publication date: 17 December 2012

Abstract: For $m,ninN$, the fractional power $Gmn$ of a graph $G$ is the $m$th power of the $n$-subdivision of $G$, where the $n$-subdivision is obtained by replacing each edge in $G$ with a path of length $n$. It was conjectured by Iradmusa that if $G$ is a connected graph with $Delta(G)ge3$ and $1<m<n$, then $chi(Gmn)=omega(Gmn)$. Here we show that the conjecture does not hold in full generality by presenting a graph $H$ for which $chi(H^{3/5})>omega(H^{3/5})$. However, we prove that the conjecture is true if $m$ is even. We also study the case when $m$ is odd, obtaining a general upper bound $chi(Gmn)leqomega(Gmn)+2$ for graphs with $Delta(G)geq4$.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

This page was built for publication: On coloring of fractional powers of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6238080)