33 citations · 164 across the 61 of their papers we have counts for
11 papers · 1 filter
Polychromatic colorings of complete graphs with respect to 1-,2-factors and Hamiltonian cycles
Maria Axenovich, John Goldwasser, Ryan Hansen +5
If G is a graph and H is a set of subgraphs of G, then an edge-coloring of G is called H-polychromatic if every graph from H gets all colors present in G on its edges. The H-polych…
The Chromatic Number of Ordered Graphs With Constrained Conflict Graphs
Maria Axenovich, Jonathan Rollin, Torsten Ueckerdt
An ordered graph is a graph whose vertex set is a subset of integers. The edges are interpreted as tuples with . For a positive integer , a matrix $M \in \mat…
High girth hypergraphs with unavoidable monochromatic or rainbow edges
Maria Axenovich, Annette Karrer
A classical result of Erdős and Hajnal claims that for any integers there is an -uniform hypergraph of girth at least with chromatic number at least . Th…
The -strong induced arboricity of a graph
Maria Axenovich, Daniel Goncalves, Jonathan Rollin +1
The induced arboricity of a graph is the smallest number of induced forests covering the edges of . This is a well-defined parameter bounded from above by the number of edge…
Avoiding patterns in matrices via a small number of changes
Maria Axenovich, Ryan R. Martin
Let be a partition of a set into nonempty subsets, and be an matrix. We say that $…
On the strong chromatic number of graphs
Maria Axenovich, Ryan R. Martin
The strong chromatic number, , of an -vertex graph is the smallest number such that after adding isolated vertices to and considering {…
A note on short cycles in a hypercube
Maria Axenovich, Ryan R. Martin
How many edges can a quadrilateral-free subgraph of a hypercube have? This question was raised by Paul Erdős about years ago. His conjecture that such a subgraph asymptoticall…
Sub-Ramsey numbers for arithmetic progressions
Maria Axenovich, Ryan R. Martin
Let the integers be assigned colors. Szemerédi's theorem implies that if there is a dense color class then there is an arithmetic progression of length three in that c…
On weighted Ramsey numbers
Maria Axenovich, Ryan Martin
The weighted Ramsey number, , is the minimum such that there is an assignment of nonnegative real numbers (weights) to the edges of with the total sum of t…
Avoiding rainbow induced subgraphs in vertex-colorings
Maria Axenovich, Ryan Martin
For a fixed graph on vertices, and a graph on at least vertices, we write if in any vertex-coloring of with colors, there is an induced sub…
Chromatic number of ordered graphs with forbidden ordered subgraphs
Maria Axenovich, Jonathan Rollin, Torsten Ueckerdt
It is well-known that the graphs not containing a given graph H as a subgraph have bounded chromatic number if and only if H is acyclic. Here we consider ordered graphs, i.e., grap…