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

DOI10.1016/J.DISC.2024.113894MaRDI QIDQ6197752zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

Cites work

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

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)