New bounds on the anti-Ramsey numbers of star graphs via maximum edge q-coloring

DOI10.1016/J.DISC.2024.113894arXiv1810.00624OpenAlexW4391201878WikidataQ129522628 ScholiaQ129522628MaRDI QIDQ6197752FDOQ6197752

Authors: L. Sunil Chandran, Talha Hashim, Dalu Jacob, Rogers Mathew, Deepak Rajendraprasad, Nitin Singh 

Publication date: 19 February 2024

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

Abstract: The anti-Ramsey number $ar(G,H)$ with input graph $G$ and pattern graph $H$, is the maximum positive integer $k$ such that there exists an edge coloring of $G$ using $k$ colors, in which there are no rainbow subgraphs isomorphic to $H$ in $G$. ($H$ is rainbow if all its edges get distinct colors). The concept of anti-Ramsey number was introduced by Erd"os, Simanovitz, and S'os in 1973. Thereafter several researchers investigated this concept in the combinatorial setting. Recently, Feng et al. revisited the anti-Ramsey problem for the pattern graph $K_{1,t}$ (for $tgeq3$) purely from an algorithmic point of view due to its applications in interference modeling of wireless networks. They posed it as an optimization problem, the maximum edge $q$-coloring problem. For a graph $G$ and an integer $qgeq2$, an edge $q$-coloring of $G$ is an assignment of colors to edges of $G$, such that edges incident on a vertex span at most $q$ distinct colors. The maximum edge $q$-coloring problem seeks to maximize the number of colors in an edge $q$-coloring of the graph $G$. Note that the optimum value of the edge $q$-coloring problem of $G$ equals $ar(G,K_{1,q+1})$. In this paper, we study $ar(G,K_{1,t})$, the anti-Ramsey number of stars, for each fixed integer $tgeq3$, both from combinatorial and algorithmic point of view. The first of our main results presents an upper bound for $ar(G,K_{1,q+1})$, in terms of number of vertices and the minimum degree of $G$. The second one improves this result for the case of triangle-free input graphs. For a positive integer $t$, let $H_t$ denote a subgraph of $G$ with maximum number of possible edges and maximum degree $t$. Our third main result presents an upper bound for $ar(G,K_{1,q+1})$ in terms of $|E(H_{q-1})|$. All our results have algorithmic consequences.

Full work available at URL: https://arxiv.org/abs/1810.00624

Recommendations

• Improved approximation for maximum edge colouring problem
• On a generalized anti-Ramsey problem
• On the anti-Ramsey number of forests
• Anti-Ramsey numbers of minimal graphs
• Anti-Ramsey numbers in complete \(k\)-partite graphs

zbMATH Keywords

approximation algorithmanti-Ramsey numbermaximum edge \(q\)-coloring problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Cites Work

• Edge-colorings with no large polychromatic stars
• An anti-Ramsey theorem on cycles
• On a conjecture of erdöus, simonovits, and sós concerning anti‐Ramsey theorems
• Title not available (Why is that?)
• On the Erdős–Simonovits–Sós Conjecture about the Anti-Ramsey Number of a Cycle
• Rainbow generalizations of Ramsey theory: A survey
• On restricted colourings of \(K_ n\)
• Approximation algorithm for maximum edge coloring
• Minimal colorings for properly colored subgraphs
• Approximation and hardness results for the maximum edge \(q\)-coloring problem
• Approximation Algorithms for Maximum Edge Coloring Problem
• On totally multicolored stars
• Improved approximation for maximum edge colouring problem

This page was built for publication: New bounds on the anti-Ramsey numbers of star graphs via maximum edge \(q\)-coloring

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