χ_D(G), |Aut(G)|, and a variant of the motion lemma
| Autor: | Sajith Padinhatteeri, Niranjan Balachandran |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
Lemma (mathematics) Algebra and Number Theory Computational complexity theory 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology Automorphism 01 natural sciences Graph Theoretical Computer Science Combinatorics Arbitrarily large 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Bipartite graph Discrete Mathematics and Combinatorics Geometry and Topology Mathematics |
| Zdroj: | Ars Mathematica Contemporanea. 12:89-109 |
| ISSN: | 1855-3974 1855-3966 |
| DOI: | 10.26493/1855-3974.848.669 |
| Popis: | The Distinguishing Chromatic Number of a graph G , denoted χ D ( G ) , was first defined in K. L. Collins and A. N. Trenk, The distinguishing chromatic number, Electron. J. Combin. 13 (2006), #R16, as the minimum number of colors needed to properly color G such that no non-trivial automorphism ϕ of the graph G fixes each color class of G . In this paper, We prove a lemma that may be considered a variant of the Motion lemma of A. Russell and R. Sundaram, A note on the asympotics and computational complexity of graph distinguishability, Electron. J. Combin. 5 (1998), #R23, and use this to give examples of several families of graphs which satisfy χ D ( G ) = χ ( G ) + 1 . We give an example of families of graphs that admit large automorphism groups in which every proper coloring is distinguishing. We also describe families of graphs with (relatively) very small automorphism groups which satisfy χ D ( G ) = χ ( G ) + 1 , for arbitrarily large values of χ ( G ) . We describe non-trivial families of bipartite graphs that satisfy χ D ( G ) > r for any positive integer r . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|