2023/12/09 by Aleksandra Gorzkowska, Gorzkowska, Aleksandra, Magdalena Prorok +1
Computer Science · #05C15 #05C20 #05C25 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2312.05564
openalex publication_date 2023/12/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider edge colorings of graphs. An edge coloring is a majority coloring if for every vertex at most half of the edges incident with it are in one color. And edge coloring is a distinguishing coloring if for every non-trivial automorphism at least one edge changes its color. We consider these two notions together. We show that every graph without pendant edges has a majority distinguishing edge coloring with at most \lceil√Δ\rceil+5 colors. Moreover, we show results for some classes of graphs and a~general result for symmetric digraphs.