Strong product of graphs

Two vertices are adjacent in the strong product when they come from pairs of vertices in the factor graphs that are either adjacent or identical.

Care should be exercised when encountering the term strong product in the literature, since it has also been used to denote the tensor product of graphs.

Together, these two kinds of edges make up the entire strong product.

[4][5] This result has been used to prove that planar graphs have bounded queue number,[4] small universal graphs and concise adjacency labeling schemes,[6][7][8][9] and bounded nonrepetitive chromatic number[10] and centered chromatic number.

[11] This product structure can be found in linear time.

[16] The clique number of the strong product of any two graphs equals the product of the clique numbers of the two graphs.

[18] A leaf power is a graph formed from the leaves of a tree by making two leaves adjacent when their distance in the tree is below some threshold

This embedding has been used in recognition algorithms for leaf powers.

, has been suggested as a possibility for a 10-chromatic biplanar graph that would improve the known bounds on the Earth–Moon problem; another suggested example is the graph obtained by removing any vertex from

In both cases, the number of vertices in these graphs is more than 9 times the size of their largest independent set, implying that their chromatic number is at least 10.