Source author record

Nathan Graber

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

On the Strong Chromatic Index of Sparse Graphs

The strong chromatic index of a graph $G$ , denoted $χ_s'(G)$ , is the least number of colors needed to edge-color $G$ so that edges at distance at most two receive distinct colors. The strong list chromatic index, denoted $χ_{s,\ell}'(G)$ , is the least integer $k$ such that if arbitrary lists of size $k$ are assigned to each edge then $G$ can be edge-colored from those lists where edges at distance at most two receive distinct colors. We use the discharging method, the Combinatorial Nullstellensatz, and computation to show that if $G$ is a subcubic planar graph with $\operatorname{girth}(G) \geq 41$ then $χ_{s,\ell}'(G) \leq 5$ , answering a question of Borodin and Ivanova [Precise upper bound for the strong edge chromatic number of sparse planar graphs, Discuss. Math. Graph Theory, 33(4), (2014) 759--770]. We further show that if $G$ is a subcubic planar graph and $\operatorname{girth}(G) \geq 30$ , then $χ_s'(G) \leq 5$ , improving a bound from the same paper. Finally, if $G$ is a planar graph with maximum degree at most four and $\operatorname{girth}(G) \geq 28$ , then $χ_s'(G) \leq 7$ , improving a more general bound of Wang and Zhao from [Odd graphs and its application on the strong edge coloring, arXiv:1412.8358] in this case.

preprint2014arXiv

Linear Turan numbers of r-uniform linear cycles and related Ramsey numbers

An $r$ -uniform hypergraph is called an $r$ -graph. A hypergraph is linear if every two edges intersect in at most one vertex. Given a linear $r$ -graph $H$ and a positive integer $n$ , the linear Turán number $ex_L(n,H)$ is the maximum number of edges in a linear $r$ -graph $G$ that does not contain $H$ as a subgraph. For each $\ell\geq 3$ , let $C^r_\ell$ denote the $r$ -uniform linear cycle of length $\ell$ , which is an $r$ -graph with edges $e_1,\ldots, e_\ell$ such that $\forall i\in [\ell-1]$ , $|e_i\cap e_{i+1}|=1$ , $|e_\ell\cap e_1|=1$ and $e_i\cap e_j=\emptyset$ for all other pairs $\{i,j\}, i\neq j$ . For all $r\geq 3$ and $\ell\geq 3$ , we show that there exist positive constants $c_{m,r}$ and $c'_{m,r}$ , depending only $m$ and $r$ , such that $ex_L(n,C^r_{2m})\leq c_{m,r} n^{1+\frac{1}{m}}$ and $ex_L(n,C^r_{2m+1})\leq c'_{m,r} n^{1+\frac{1}{m}}$ . This answers a question of Kostochka, Mubayi, and Verstraëte. For even cycles, our result extends the result of Bondy and Simonovits on the Turán numbers of even cycles to linear hypergraphs. Using our results on linear Turán numbers we also obtain bounds on the cycle-complete hypergraph Ramsey numbers. We show that there are positive constants $a_{m,r}$ and $b_{m,r}$ , depending only on $m$ and $r$ , such that $R(C^r_{2m}, K^r_t)\leq a_{m,r} (\frac{t}{\ln t})^\frac{m}{m-1}$ and $R(C^r_{2m+1}, K^r_t)\leq b_{m,r} t^\frac{m}{m-1}$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.