Asymmetric colorings of products of graphs and digraphs

DOI10.1016/J.DAM.2018.12.023MaRDI QIDQ2026319zbMATH OpenOpenAlexWikidataFDO

Authors Izak Broere, Wilfried Imrich, Rafał Kalinowski, Monika Pilśniak

Publication date 19 May 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2018.12.023

zbMATH Keywords

asymmetric coloringsautomorphismsCartesian productsdirect productsstrong productsvertex colorings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Review text

The asymmetric coloring number (also called the distinguishing number) of a graph \(G\) is the least integer \(d\) such that there is a \(d\)-labeling of the vertices of \(G\) that is not preserved by any nontrivial automorphism of \(G\). The authors study the asymmetric coloring number of all main graph products: the strong, the direct, and the Cartesian product. Factors of the strong and the direct product considered in the paper are restricted to finite graphs and digraphs, while for the Cartesian product, previous results from [\textit{E. Estaji} et al., Discuss. Math., Graph Theory 37, No. 1, 155--164 (2017; Zbl 1354.05065)] are extended to finite or infinite digraphs with or without loops. It is shown that in most cases, the product of two graphs has an asymmetric 2-coloring. In order to obtain the results, the authors use the fact that all finite graphs have prime factorizations with respect to the strong and the direct product. Moreover, these factorizations are essentially. They also exploit the relationship between the automorphism group of a product of prime graphs with the groups of the factors.

Recommendations

• Distinguishing Cartesian products of countable graphs
• Distinguishing index of graphs with simple automorphism groups
• Game distinguishing numbers of Cartesian products
• The distinguishing chromatic number of Cartesian products of two complete graphs
• Precise bounds for the distinguishing index of the Cartesian product
• Number of colors needed to break symmetries of a graph by an arbitrary edge coloring
• The distinguishing number of Cartesian products of complete graphs
• scientific article; zbMATH DE number 5778120
• Distinguishing chromatic numbers of complements of Cartesian products of complete graphs
• Distinguishing number of hierarchical products of graphs

Cites work

• Asymmetric trees with two prescribed degrees
• Asymmetrization of infinite trees
• Cardinal multiplication of structures with a reflexive relation
• Distinguishing Cartesian powers of graphs
• Distinguishing Cartesian products of countable graphs
• Factoring directed graphs with respect to the cardinal product in polynomial time
• Factoring directed graphs with respect to the cardinal product in polynomial time II
• Finding the prime factors of strong direct product graphs in polynomial time
• Fixed elements of infinite trees
• Graph multiplication
• Handbook of product graphs
• scientific article; zbMATH DE number 3308993 (Why is no real title available?)
• On Cartesian skeletons of graphs
• On the Cartesian skeleton and the factorization of the strong product of digraphs
• Refinement properties for relational structures
• Regular orbits of permutation groups on the power set
• Symmetry breaking in graphs
• The Cartesian product of graphs with loops

Cited in

(1)

• Asymmetric edge-colorings of graphs with three colors

This page was built for publication: Asymmetric colorings of products of graphs and digraphs

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