Source author record

Bogdan Oporowski

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

3works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

A Note On Immersion Intertwines Of Infinite Graphs

We present a construction of two infinite graphs $G_1$ and $G_2$ , and of an infinite set $\mathscr{F}$ of graphs such that $\mathscr{F}$ is an antichain with respect to the immersion relation and, for each graph $G$ in $\mathscr{F}$ , both $G_1$ and $G_2$ are subgraphs of $G$ , but no graph properly immersed in $G$ admits an immersion of $G_1$ and of $G_2$ . This shows that the class of infinite graphs ordered by the immersion relation does not have the finite intertwine property.

preprint2013arXiv

Characterizing 2-crossing-critical graphs

It is very well-known that there are precisely two minimal non-planar graphs: $K_5$ and $K_{3,3}$ (degree 2 vertices being irrelevant in this context). In the language of crossing numbers, these are the only 1-crossing-critical graphs: they each have crossing number at least one, and every proper subgraph has crossing number less than one. In 1987, Kochol exhibited an infinite family of 3-connected, simple 2-crossing-critical graphs. In this work, we: (i) determine all the 3-connected 2-crossing-critical graphs that contain a subdivision of the Möbius Ladder $V_{10}$ ; (ii) show how to obtain all the not 3-connected 2-crossing-critical graphs from the 3-connected ones; (iii) show that there are only finitely many 3-connected 2-crossing-critical graphs not containing a subdivision of $V_{10}$ ; and (iv) determine all the 3-connected 2-crossing-critical graphs that do not contain a subdivision of $V_{8}$ .

preprint2010arXiv

Large Non-Planar Graphs and an Application to Crossing-Critical Graphs

We prove that, for every positive integer k, there is an integer N such that every 4-connected non-planar graph with at least N vertices has a minor isomorphic to K_{4,k}, the graph obtained from a cycle of length 2k+1 by adding an edge joining every pair of vertices at distance exactly k, or the graph obtained from a cycle of length k by adding two vertices adjacent to each other and to every vertex on the cycle. We also prove a version of this for subdivisions rather than minors, and relax the connectivity to allow 3-cuts with one side planar and of bounded size. We deduce that for every integer k there are only finitely many 3-connected 2-crossing-critical graphs with no subdivision isomorphic to the graph obtained from a cycle of length 2k by joining all pairs of diagonally opposite vertices.

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.