Martin Rolek

activity

20162025

most citedFat-triangle linkage and kite-linked graphs

2 citations · 6 across the 12 of their papers we have counts for

collaborators

13 papers

math.CO2025

Connectivity of contraction-critical graphs

Michael Lafferty, Runrun Liu, Martin Rolek +1

Contraction-critical graphs came from the study of minimal counterexamples to Hadwiger's conjecture. A graph is $k$ -contraction-critical if it is $k$ -chromatic, but any proper mino…

math.CO2022

Properties of $8$ -contraction-critical graphs with no $K_{7}$ minor

Martin Rolek, Zi-Xia Song, Robin Thomas

Motivated by the famous Hadwiger's Conjecture, we study the properties of $8$ -contraction-critical graphs with no $K_{7}$ minor; we prove that every $8$ -contraction-critical graph wi…

math.CO2021

Sufficient conditions for 2-dimensional global rigidity

Xiaofeng Gu, Wei Meng, Martin Rolek +2

The 2-dimensional global rigidity has been shown to be equivalent to 3-connectedness and redundant rigidity by a combination of two results due to Jackson and Jordán, and Connelly,…

math.CO2019★ 1 cited

Connectivity for Kite-Linked Graphs

Chris Stephens, Dong Ye

For a given graph $H$ , a graph $G$ is $H$ -linked if, for every injection $φ : V (H) \to V (G)$ , the graph $G$ contains a subdivision of $H$ with $φ (v)$ corresponding to $v$ , for each…

math.CO2019★ 1 cited

Packing $(1, 1, 2, 2)$ -coloring of some subcubic graphs

Runrun Liu, Xujun Liu, Martin Rolek +1

For a sequence of non-decreasing positive integers $S = (s_{1}, \dots, s_{k})$ , a packing $S$ -coloring is a partition of $V (G)$ into sets $V_{1}, \dots, V_{k}$ such that for each $1\leq…

math.CO2019★ 2 cited

Fat-triangle linkage and kite-linked graphs

Runrun Liu, Martin Rolek, Gexin Yu

For a multigraph $H$ , a graph $G$ is $H$ -linked if every injective mapping $ϕ : V (H) \to V (G)$ can be extended to an $H$ -subdivision in $G$ . We study the minimum connectivity require…

math.CO2018

Minimum degree condition for a graph to be knitted

Runrun Liu, Martin Rolek, Gexin Yu

For a positive integer $k$ , a graph is $k$ -knitted if for each $k$ -subset $S$ of vertices, and every partition of $S$ into disjoint parts $S_{1}, \dots, S_{t}$ for some $t \geq 1$ , one…

math.CO2018

DP-3-coloring of planar graphs without $4, 9$ -cycles and two cycles from ${5, 6, 7, 8}$

Runrun Liu, Sarah Loeb, Martin Rolek +2

A generalization of list-coloring, now known as DP-coloring, was recently introduced by Dvořák and Postle. Essentially, DP-coloring assigns an arbitrary matching between lists of c…

math.CO2018

The extremal function for $K_{9}^{=}$ minors

Martin Rolek

We prove the extremal function for $K_{9}^{=}$ minors, where $K_{9}^{=}$ denotes the complete graph $K_{9}$ with two edges removed. In particular, we show that any graph with $n$ vertices an…

math.CO2018

Saturation numbers for Ramsey-minimal graphs

Martin Rolek, Zi-Xia Song

Given graphs $H_{1}, \dots, H_{t}$ , a graph $G$ is $(H_{1}, \dots, H_{t})$ -Ramsey-minimal if every $t$ -coloring of the edges of $G$ contains a monochromatic $H_{i}$ in color $i$ for some $i\…

math.CO2016

Double-critical graph conjecture for claw-free graphs

Martin Rolek, Zi-Xia Song

A connected graph $G$ with chromatic number $t$ is double-critical if $G \ {x, y}$ is $(t - 2)$ -colorable for each edge $x y \in E (G)$ . The complete graphs are the only k…

math.CO2016★ 1 cited

Coloring Graphs with Forbidden Minors

Martin Rolek, Zi-Xia Song

Hadwiger's conjecture from 1943 states that for every integer $t \geq 1$ , every graph either can be $t$ -colored or has a subgraph that can be contracted to the complete graph on $t + 1$ …

math.CO2016★ 1 cited

Clique Minors in Double-critical Graphs

Martin Rolek, Zi-Xia Song

A connected $t$ -chromatic graph $G$ is \dfn{double-critical} if $G \ {u, v}$ is $(t - 2)$ -colorable for each edge $uv \in E (G)$ . A long standing conjecture of Erdős and Lová…

Connectivity of contraction-critical graphs

Properties of 8-contraction-critical graphs with no K7​ minor

Sufficient conditions for 2-dimensional global rigidity

Connectivity for Kite-Linked Graphs

Packing (1,1,2,2)-coloring of some subcubic graphs

Fat-triangle linkage and kite-linked graphs

Minimum degree condition for a graph to be knitted

DP-3-coloring of planar graphs without 4,9-cycles and two cycles from {5,6,7,8}

The extremal function for K9=​ minors

Saturation numbers for Ramsey-minimal graphs

Double-critical graph conjecture for claw-free graphs

Coloring Graphs with Forbidden Minors

Clique Minors in Double-critical Graphs

Properties of $8$ -contraction-critical graphs with no $K_{7}$ minor

Packing $(1, 1, 2, 2)$ -coloring of some subcubic graphs

DP-3-coloring of planar graphs without $4, 9$ -cycles and two cycles from ${5, 6, 7, 8}$

The extremal function for $K_{9}^{=}$ minors