Ingo Schiermeyer

collaborators

Showing math.COShow all

6 papers · 1 filter

math.CO2026

Lower bounds on the independence number of a graph in terms of degrees

Jochen Harant, Ingo Schiermeyer

Given an integer $I^ \geq 3$ , let $G_{I^}$ be the set of connected graphs $G \neq = K_{I^ + 1}$ with maximum degree $I^$ and, for $i = 1, \dots, I^$ , let $V_{i} (G)$ be the set of verti…

math.CO2026

Asymptotic Bounds for t(3,n) and an Application to t(4,n)

Meng Ji, Yaping Mao, Ingo Schiermeyer

A set of vertices $X \subseteq V$ in a simple graph $G (V, E)$ is irredundant if each vertex $x \in X$ is either isolated in the induced subgraph $G [X]$ or else has a private neighbor…

math.CO2026

On 3-colorability of (claw, diamond)-free graphs

Nadzieja Hodur, Monika PilÅniak, Magdalena Prorok +1

The $3$ -colorability problem is a well-known NP-complete problem and it remains NP-complete for $(c l a w, d iam o n d, K_{4})$ -free graphs. Recently, $3$ -colorability has been also conside…

math.CO2025

On the independence number in subcubic graphs

Jochen Harant, Ingo Schiermeyer

For a connected subcubic graph $G \neq = K_{1}$ let $V_{i} (G) = {v \in V (G) ∣ d_{G} (v) = i}$ for $1 \leq i \leq 3.$ Given $c_{1}, c_{2}, c_{3} \in R^{+}$ and $d \in R$ , we sho…

math.CO2025

On $k$ -colorability of $(b u l l, H)$ -free graphs

Nadzieja Hodur, Monika PilÅniak, Magdalena Prorok +1

The $3$ -colorability problem is a well-known NP-complete problem and it remains NP-complete for $b u l l$ -free graphs, where a $b u l l$ is the graph consisting of a $K_{3}$ with two penda…

math.CO2024

On 3-colourability of $(b u l l, H)$ -free graphs

Nadzieja Hodur, Monika PilÅniak, Magdalena Prorok +1

The $3$ -colourability problem is a well-known NP-complete problem and it remains NP-complete for $b u l l$ -free graphs, where $b u l l$ is the graph consisting of $K_{3}$ with two pendant…

Lower bounds on the independence number of a graph in terms of degrees

Asymptotic Bounds for t(3,n) and an Application to t(4,n)

On 3-colorability of (claw, diamond)-free graphs

On the independence number in subcubic graphs

On k-colorability of (bull,H)-free graphs

On 3-colourability of (bull,H)-free graphs

On $k$ -colorability of $(b u l l, H)$ -free graphs

On 3-colourability of $(b u l l, H)$ -free graphs