Source author record

Ingo Schiermeyer

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

8works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Homogeneous sets, clique-separators, critical graphs, and optimal $χ$ -binding functions

Given a set $\mathcal{H}$ of graphs, let $f_\mathcal{H}^\star\colon \mathbb{N}_{>0}\to \mathbb{N}_{>0}$ be the optimal $χ$ -binding function of the class of $\mathcal{H}$ -free graphs, that is, $f_\mathcal{H}^\star(ω)=\max\{χ(G): G\text{ is } \mathcal{H}\text{-free, } ω(G)=ω\}.$ In this paper, we combine the two decomposition methods by homogeneous sets and clique-separators in order to determine optimal $χ$ -binding functions for subclasses of $P_5$ -free graphs and of $(C_5,C_7,\ldots)$ -free graphs. In particular, we prove the following for each $ω\geq 1$ : (i) $\ f_{\{P_5,banner\}}^\star(ω)=f_{3K_1}^\star(ω)\in Θ(ω^2/\log(ω)),$ (ii) $\ f_{\{P_5,co-banner\}}^\star(ω)=f^\star_{\{2K_2\}}(ω)\in\mathcal{O}(ω^2),$ (iii) $\ f_{\{C_5,C_7,\ldots,banner\}}^\star(ω)=f^\star_{\{C_5,3K_1\}}(ω)\notin \mathcal{O}(ω),$ and (iv) $\ f_{\{P_5,C_4\}}^\star(ω)=\lceil(5ω-1)/4\rceil.$ We also characterise, for each of our considered graph classes, all graphs $G$ with $χ(G)>χ(G-u)$ for each $u\in V(G)$ . From these structural results, we can prove Reed's conjecture -- relating chromatic number, clique number, and maximum degree of a graph -- for $(P_5,banner)$ -free graphs.

preprint2022arXiv

Loose edge-connection of graphs

In the last years, connection concepts such as rainbow connection and proper connection appeared in graph theory and obtained a lot of attention. In this paper, we investigate the loose edge-connection of graphs. A connected edge-coloured graph $G$ is loose edge-connected if between any two of its vertices there is a path of length one, or a bi-coloured path of length two, or a path of length at least three with at least three colours used on its edges. The minimum number of colours, used in a loose edge-colouring of $G$ , is called the loose edge-connection number and denoted $\lec(G)$. We determine the precise value of this parameter for any simple graph $G$ of diameter at least 3. We show that deciding, whether $\lec(G) = 2$ for graphs $G$ of diameter 2, is an NP-complete problem. Furthermore, we characterize all complete bipartite graphs $K_{r,s}$ with $\lec(K_{r,s}) = 2$.

preprint2015arXiv

Local Connectivity, Local Degree Conditions, some Forbidden Induced Subgraphs, and Cycle Extendability

The research in the present paper was motivated by the conjecture of Ryjáček that every locally connected graph is weakly pancyclic. For a connected locally connected graph $G$ of order at least $3$ , our results are as follows: If $G$ is $(K_1+(K_1\cup K_2))$ -free, then $G$ is weakly pancyclic. If $G$ is $(K_1+(K_1\cup K_2))$ -free, then $G$ is fully cycle extendable if and only if $2δ(G)\geq n(G)$ . If $G$ is $\{ K_1+K_1+\bar{K}_3,K_1+P_4\}$ -free or $\{ K_1+K_1+\bar{K}_3,K_1+(K_1\cup P_3)\}$ -free, then $G$ is fully cycle extendable. If $G$ is distinct from $K_1+K_1+\bar{K}_3$ and $\{ K_1+P_4,K_{1,4},K_2+(K_1\cup K_2)\}$ -free, then $G$ is fully cycle extendable. Furthermore, if $G$ is a connected graph of order at least $3$ such that $|N_G(u)\cap N_G(v)\cap N_G(w)|>|N_G(u)\setminus (N_G[v]\cup N_G[w])|$ for every induced path $vuw$ of order $3$ in $G$ , then $G$ is fully cycle extendable, which implies that every connected locally Ore or locally Dirac graph of order at least $3$ is fully cycle extendable.

preprint2015arXiv

On star-wheel Ramsey numbers

For two given graphs $G_1$ and $G_2$ , the Ramsey number $R(G_1,G_2)$ is the least integer $r$ such that for every graph $G$ on $r$ vertices, either $G$ contains a $G_1$ or $\bar{G}$ contains a $G_2$ . In this note, we determined the Ramsey number $R(K_{1,n},W_m)$ for even $m$ with $n+2\leq m\leq 2n-2$ , where $W_m$ is the wheel on $m+1$ vertices, i.e., the graph obtained from a cycle $C_m$ by adding a vertex $v$ adjacent to all vertices of the $C_m$ .

preprint2013arXiv

Graphs with $4$ -rainbow index $3$ and $n-1$

Let $G$ be a nontrivial connected graph with an edge-coloring $c:E(G)\rightarrow \{1,2,\ldots,q\},$ $q\in \mathbb{N}$ , where adjacent edges may be colored the same. A tree $T$ in $G$ is called a $rainbow~tree$ if no two edges of $T$ receive the same color. For a vertex set $S\subseteq V(G)$ , a tree that connects $S$ in $G$ is called an {\it $S$ -tree}. The minimum number of colors that are needed in an edge-coloring of $G$ such that there is a rainbow $S$ -tree for every $k$ -set $S$ of $V(G)$ is called the {\it $k$ -rainbow index} of $G$ , denoted by $rx_k(G)$ . Notice that an lower bound and an upper bound of the $k$ -rainbow index of a graph with order $n$ is $k-1$ and $n-1$ , respectively. Chartrand et al. got that the $k$ -rainbow index of a tree with order $n$ is $n-1$ and the $k$ -rainbow index of a unicyclic graph with order $n$ is $n-1$ or $n-2$ . Li and Sun raised the open problem of characterizing the graphs of order $n$ with $rx_k(G)=n-1$ for $k\geq 3$ . In early papers we characterized the graphs of order $n$ with 3-rainbow index 2 and $n-1$ . In this paper, we focus on $k=4$ , and characterize the graphs of order $n$ with 4-rainbow index 3 and $n-1$ , respectively.

preprint2012arXiv

Rainbow numbers for graphs with cyclomatic number at most two

For a given graph H and n ? 1; let f(n;H) denote the maximum number m for which it is possible to colour the edges of the complete graph Kn with m colours in such a way that each subgraph H in Kn has at least two edges of the same colour. Equivalently, any edge-colouring of Kn with at least rb(n;H) = f(n;H)+1 colours contains a rainbow copy of H: The numbers f(n;H) and rb(Kn;H) are called anti-ramsey numbers and rainbow numbers, respectively. In this paper we will classify the rainbow number for a given graph H with respect to its cyclomatic number. Let H be a graph of order p >= 4 and cyclomatic number v(H) >= 2: Then rb(Kn;H) cannot be bounded from above by a function which is linear in n: If H has cyclomatic number v(H) = 1; then rb(Kn;H) is linear in n: We will compute all rainbow numbers for the bull B; which is the unique graph with 5 vertices and degree sequence (1; 1; 2; 3; 3): Furthermore, we will compute some rainbow numbers for the diamond D = K_4 - e; for K_2;3; and for the house H (complement of P_5).

preprint2011arXiv

Rainbow connection number of dense graphs

An edge-colored graph $G$ is rainbow connected, if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph $G$ , denoted $rc(G)$ , is the smallest number of colors that are needed in order to make $G$ rainbow connected. In this paper we show that $rc(G)\leq 3$ , if $|E(G)|\geq {{n-2}\choose 2}+2$ , and $rc(G)\leq 4$ , if $|E(G)|\geq {{n-3}\choose 2}+3$ . These bounds are sharp.

preprint2011arXiv

The rainbow connection number of 2-connected graphs

The rainbow connection number of a graph G is the least number of colours in a (not necessarily proper) edge-colouring of G such that every two vertices are joined by a path which contains no colour twice. Improving a result of Caro et al., we prove that the rainbow connection number of every 2-connected graph with n vertices is at most the ceiling of n/2. The bound is optimal.

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.

Ingo Schiermeyer

Research overview

Is this your work?

8 publications

Homogeneous sets, clique-separators, critical graphs, and optimal $χ$ -binding functions

Loose edge-connection of graphs

Local Connectivity, Local Degree Conditions, some Forbidden Induced Subgraphs, and Cycle Extendability

On star-wheel Ramsey numbers

Graphs with $4$ -rainbow index $3$ and $n-1$

Rainbow numbers for graphs with cyclomatic number at most two

Rainbow connection number of dense graphs

The rainbow connection number of 2-connected graphs

See the researcher in context

Building this map preview

Ingo Schiermeyer

Research overview

Is this your work?

8 publications

Homogeneous sets, clique-separators, critical graphs, and optimal χχχ-binding functions

Loose edge-connection of graphs

Local Connectivity, Local Degree Conditions, some Forbidden Induced Subgraphs, and Cycle Extendability

On star-wheel Ramsey numbers

Graphs with 444-rainbow index 333 and n−1n-1n−1

Rainbow numbers for graphs with cyclomatic number at most two

Rainbow connection number of dense graphs

The rainbow connection number of 2-connected graphs

See the researcher in context

Building this map preview

Homogeneous sets, clique-separators, critical graphs, and optimal $χ$ -binding functions

Graphs with $4$ -rainbow index $3$ and $n-1$