DMS Combinatorics Seminar

Speaker: Songling Shan (Auburn University)

Title: Vertex-distinguishing and sum-distinguishing edge coloring of regular graphs

Abstract: Given an integer \(k\ge1\), an edge-\(k\)-coloring of a graph \(G\) is an assignment of \(k\) colors \(1,\ldots,k\) to the edges of \(G\) such that no two adjacent edges receive the same color. A vertex-distinguishing (resp., sum-distinguishing) edge-\(k\)-coloring of \(G\) is an edge-\(k\)-coloring such that for any two distinct vertices \(u\) and \(v\), the set (resp., sum) of colors taken from all the edges incident with \(u\) is different from that taken from all the edges incident with \(v\). The vertex-distinguishing chromatic index (resp., sum-distinguishing chromatic index), denoted \(\chi'_{vd}(G)\) (resp.,  \(\chi'_{sd}(G)\)), is the smallest value \(k\) such that \(G\) has a vertex-distinguishing edge-\(k\)-coloring (resp., sum-distinguishing edge-\(k\)-coloring). Let \(G\) be a \(d\)-regular graph on \(n\) vertices, where \(n\) is even and sufficiently large. We show that \(\chi'_{vd}(G) =d+2\) if \(d\) is arbitrarily close to \(n/2\) from above, and \(\chi'_{sd}(G) =d+2\) if \(d\ge \frac{2n}{3}\).