Exact values of defective Ramsey numbers in graph classes

DOI10.1016/J.DISOPT.2021.100673MaRDI QIDQ2067502zbMATH OpenOpenAlexFDO

Authors Yunus Emre Demirci, Tınaz Ekim, M. Yildiz, John Gimbel

Publication date 18 January 2022

Published in Discrete Optimization (Search for Journal in Brave)

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

zbMATH Keywords

split graphforestcacticograph\(k\)-dense set\(k\)-sparse set

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55)

Abstract: Given a graph $G$, a $k$-sparse $j$-set is a set of $j$ vertices inducing a subgraph with maximum degree at most $k$. A $k$-dense $i$-set is a set of $i$ vertices that is $k$-sparse in the complement of $G$. As a generalization of Ramsey numbers, the $k$-defective Ramsey number $R_k^{mathcalG}(i,j)$ for the graph class $mathcalG$ is defined as the smallest natural number $n$ such that all graphs on $n$ vertices in the class $mathcalG$ have either a $k$-dense $i$-set or a $k$-sparse $j$-set. In this paper, we examine $R_k^{mathcalG}(i,j)$ where $mathcalG$ represents various graph classes. In forests and cographs, we give formulas for all defective Ramsey numbers. In cacti, bipartite graphs and split graphs, we provide defective Ramsey numbers in most of the cases and point out open questions, formulated as conjectures if possible.

Recommendations

• Defective Ramsey numbers and defective cocolorings in some subclasses of perfect graphs
• Advances on defective parameters in graphs
• Small 1-defective Ramsey numbers in perfect graphs
• Some defective parameters in graphs
• Multipartite graph-sparse graph Ramsey numbers

Cites work

• Advances on defective parameters in graphs
• Complement reducible graphs
• Graph classes and Ramsey numbers
• Independence in graphs with maximum degree four
• Longest paths and cycles in K1,3-free graphs
• Lower bounds on size and independence inK4-free graphs
• On 1-dependent ramsey numbers for graphs
• On subgraphs without large components.
• Planar Ramsey numbers
• Small 1-defective Ramsey numbers in perfect graphs
• Some Ramsey-Type Numbers and the Independence Ratio
• Some defective parameters in graphs

Cited in

(3)

• Small 1-defective Ramsey numbers in perfect graphs
• Advances on defective parameters in graphs
• Defective Ramsey numbers and defective cocolorings in some subclasses of perfect graphs

This page was built for publication: Exact values of defective Ramsey numbers in graph classes

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