The distinguishing chromatic number of Kneser graphs

MaRDI QIDQ1953404zbMATH OpenFDO

Authors Zhongyuan Che, Karen L. Collins

Publication date 7 June 2013

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i1p23

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

distinguishing chromatic numberdistinguishing numberKneser graphsproper coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Review text

Summary: A labeling \(f: V(G) \rightarrow \{1, 2, \ldots, d\}\) of the vertex set of a graph \(G\) is said to be proper \(d\)-distinguishing if it is a proper coloring of \(G\) and any nontrivial automorphism of \(G\) maps at least one vertex to a vertex with a different label. The distinguishing chromatic number of \(G\), denoted by \(\chi_D(G)\), is the minimum \(d\) such that \(G\) has a proper \(d\)-distinguishing labeling. Let \(\chi(G)\) be the chromatic number of \(G\) and \(D(G)\) be the distinguishing number of \(G\). Clearly, \(\chi_D(G) \geq \chi(G)\) and \(\chi_D(G) \geq D(G)\). \textit{K. L. Collins} et al. [ibid. 16, No. 1, Research Paper R88, 14 p. (2009; Zbl 1186.05051)] have given a tight upper bound on \(\chi_D(G)-\chi(G)\) in terms of the order of the automorphism group of \(G\), improved when the automorphism group of \(G\) is a finite abelian group. The Kneser graph \(K(n,r)\) is a graph whose vertices are the \(r\)-subsets of an \(n\) element set, and two vertices of \(K(n,r)\) are adjacent if their corresponding two \(r\)-subsets are disjoint. In this paper, we provide a class of graphs \(G\), namely Kneser graphs \(K(n,r)\), whose automorphism group is the symmetric group, \(S_n\), such that \(\chi_D(G) - \chi(G) \leq 1\). In particular, we prove that \(\chi_D(K(n,2))=\chi(K(n,2))+1\) for \(n\geq 5\). In addition, we show that \(\chi_D(K(n,r))=\chi(K(n,r))\) for \(n \geq 2r+1\) and \(r\geq 3\).

Recommendations

• The list distinguishing number of Kneser graphs
• Using determining sets to distinguish Kneser graphs
• The distinguishing chromatic number of line graphs of complete graphs
• Vertex transitive graphs \(G\) with \(\chi_D (G)>\chi(G)\) and small automorphism group
• Bounds on the distinguishing chromatic number

Cited in

(15)

• The list distinguishing number of Kneser graphs
• Upper bounds on the locating chromatic number of trees
• On the chromatic number of a subgraph of the Kneser graph
• Equitable distinguishing chromatic number
• Bounds on the distinguishing chromatic number
• scientific article; zbMATH DE number 4214034 (Why is no real title available?)
• scientific article; zbMATH DE number 1043908 (Why is no real title available?)
• Vertex transitive graphs \(G\) with \(\chi_D (G)>\chi(G)\) and small automorphism group
• The distinguishing chromatic number of line graphs of complete graphs
• Total dominator chromatic number of Kneser graphs
• The determining number and cost of 2-distinguishing of select Kneser graphs
• On the distinguishing chromatic number of the Kronecker products of graphs
• Distinguishing chromatic numbers of complements of Cartesian products of complete graphs
• Distinguishing chromatic number of the hierarchical product of graphs
• Using determining sets to distinguish Kneser graphs

This page was built for publication: The distinguishing chromatic number of Kneser graphs

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