University of Haifa

output

19922026

most citedThe new world atlas of artificial night sky brightness

1.7k citations

Showing math.COShow all

115 papers · 1 filter

math.CO2025

Acyclic subgraphs of digraphs with high chromatic number

Raphael Yuster

For a digraph $G$ , let $f (G)$ be the maximum chromatic number of an acyclic subgraph of $G$ . For an $n$ -vertex digraph $G$ it is proved that $f (G) \geq n^{5/9 - o (1)} s^{- 14/9}$ where…

math.CO2024★ 1 cited

Monochromatic graph decompositions inspired by anti-Ramsey theory and the odd-coloring problem

Yair Caro, Zsolt Tuza

We consider extremal edge-coloring problems inspired by the theory of anti-Ramsey / rainbow coloring, and further by odd-colorings and conflict-free colorings. Let $G$ be a graph,…

math.CO2024★ 3 cited

Symplectic geometry of electrical networks

Boris Bychkov, Vassily Gorbounov, Lazar Guterman +1

In this paper we relate a well-known in symplectic geometry compactification of the space of symmetric bilinear forms considered as a chart of the Lagrangian Grassmannian to the sp…

math.CO2024

Path-monochromatic bounded depth rooted trees in (random) tournaments

Raphael Yuster

An edge-colored rooted directed tree (aka arborescence) is path-monochromatic if every path in it is monochromatic. Let $k, ℓ$ be positive integers. For a tournament $T$ , let $f_…

math.CO2024

Highly connected graphs have highly connected spanning bipartite subgraphs

Raphael Yuster

For integers $k, n$ with $1 \leq k \leq n /2$ , let $f (k, n)$ be the smallest integer $t$ such that every $t$ -connected $n$ -vertex graph has a spanning bipartite $k$ -connected subgraph.…

math.CO2024

Sorting inversion sequences

Toufik Mansour, Howard Skogman, Rebecca Smith

We consider the avoidance of patterns in inversion sequences that relate sorting via sorting machines including data structures such as pop stacks and stacks. Such machines have be…