On small balanceable, strongly-balanceable and omnitonal graphs

DOI10.7151/DMGT.2342zbMATH Open1493.05098arXiv1908.08237OpenAlexW3038815349MaRDI QIDQ2158200FDOQ2158200

Authors: Yair Caro, Josef Lauri, Christina Zarb 

Publication date: 26 July 2022

Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Abstract: In Ramsey theory for graphs we are given a graph $G$ and we are required to find the least $n_0$ such that, for any $ngeq{n}_0$, any red/blue colouring of the edges of $K_n$ gives a subgraph $G$ all of whose edges are blue or all are red. Here we shall be requiring that, for any red/blue colouring of the edges of $K_n$, there must be a copy of $G$ such that its edges are partitioned equally as red or blue (or the sizes of the colour classes differs by one in the case when $G$ has an odd number of edges). This introduces the notion of balanceable graphs and the balance number of $G$ which, if it exists, is the minimum integer bal$(n,G)$ such that, for any red/blue colouring of $E(K_n)$ with more than bal$(n,G)$ edges of either colour, $K_n$ will contain a balanced coloured copy of $G$ as described above. This parameter was introduced by Caro, Hansberg and Montejano in cite{2018arXivCHM}. There, the authors also introduce the strong balance number sbal$(n,G)$ and the more general omnitonal number ot$(n,G)$ which requires copies of $G$ containing a complete distribution of the number of red and blue edges over $E(G)$. In this paper we shall catalogue bal$(n,G)$, sbal$(n,G)$ and ot$(n,G)$ for all graphs $G$ on at most four edges. We shall be using some of the key results of Caro et al, which we here reproduce in full, as well as some new results which we prove here. For example, we shall prove that the union of two bipartite graphs with the same number of edges is always balanceable.

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

Recommendations

• Unavoidable chromatic patterns in 2‐colorings of the complete graph
• On the balanceability of some graph classes
• A note on totally-omnitonal graphs
• scientific article; zbMATH DE number 125598
• The balancing number and generalized balancing number of some graph classes

zbMATH Keywords

edge-colouringbalanceable graphsomnitonal graphszero-sum Ramsey

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Cites Work

• On maximal paths and circuits of graphs
• The history of degenerate (bipartite) extremal graph problems
• All Ramsey numbers for cycles in graphs
• A note on the Turán function of even cycles
• Title not available (Why is that?)
• The Ramsey number for stripes
• Avoiding zero-sum subsequences of prescribed length over the integers
• An analogue of the Erdős-Ginzburg-Ziv theorem over \(\mathbb{Z}\)
• Zero-sum subsequences in bounded-sum \(\{-1,1\}\)-sequences
• Zero-sum \(K_m\) over \(\mathbb{Z}\) and the story of \(K_4\)
• On zero-sum and almost zero-sum subgraphs over \(\mathbb Z\)
• Zero-sum subsequences in bounded-sum \(\{-r,s\}\)-sequences
• Zero-sum analogues of van der Waerden's theorem on arithmetic progressions
• Turán theorems for unavoidable patterns
• Zero-sum generalized Schur numbers

Cited In (4)

• On the balanceability of some graph classes
• Unavoidable chromatic patterns in 2‐colorings of the complete graph
• On balanceable and simply balanceable regular graphs
• The balancing number and generalized balancing number of some graph classes

This page was built for publication: On small balanceable, strongly-balanceable and omnitonal graphs

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