Coloring the square of the Cartesian product of two cycles (Q708380): Difference between revisions

From MaRDI portal
Normalize DOI.
Normalize DOI.
 
Property / DOI
 
Property / DOI: 10.1016/J.DISC.2010.05.011 / rank
Normal rank
 
Property / DOI
 
Property / DOI: 10.1016/J.DISC.2010.05.011 / rank
 
Normal rank

Latest revision as of 01:25, 10 December 2024

scientific article
Language Label Description Also known as
English
Coloring the square of the Cartesian product of two cycles
scientific article

    Statements

    Coloring the square of the Cartesian product of two cycles (English)
    0 references
    0 references
    0 references
    11 October 2010
    0 references
    The \textit{square} \(G^2\) of a graph \(G\) is given by \(V(G^2)=V(G)\) and \(\{u,v\} \in E(G^2)\) if and only if \(\{u,v\} \in E(G)\) or \(u\) and \(v\) have a common neighbour. The Cartesian product \(G \square H\) of given graphs \(G\) and \(H\) is the graph with vertex set \(V(G)\times V(H)\) where two vertices \((u_1, v_1)\) and \((u_2, v_2)\) are adjacent if and only if either \(u_1=u_2\) and \(\{v_1,v_2\}\in E(H)\) or \(v_1=v_2\) and \(\{u_1,u_2\}\in E(G)\). It is shown that the chromatic number of the Cartesian product \(C_m\square C_n\) of two cycles is at most 7 except when \((m,n)\) is \((3, 3)\), in which case the value is 9, and when \((m, n)\) is \((4, 4)\) or \((3, 5)\), in which case the value is 8. Moreover, it is conjectured that whenever \(G=C_m\square C_n\), the chromatic number of \(G^2\) equals \(\lceil mn/ \alpha(G^2)\rceil\), where \(\alpha(G^2)\) denotes the maximum size of an independent set in \(G^2\).
    0 references
    chromatic number
    0 references
    square of graphs
    0 references
    distance 2-colouring
    0 references
    Cartesian product
    0 references
    cycle
    0 references

    Identifiers