Bogdan Oporowski
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Bogdan Oporowski has a total of 11 co-authors. Here are the top co-authors by number of shared publications:
- Guoli Ding
Mathematics Department, Louisiana State University, Baton Rouge, Louisiana 70803
3 shared publications - Daniel P. Sanders
Department of Mathematics, Princeton University; Princeton, New Jersey 08544, USA
1 shared publication - Daxian Zhao
School of Life Sciences, Nanchang University, Nanchang 330031, China
1 shared publication - Dirk Vertigan
Louisiana State University
1 shared publication - Drago Bokal
Univerza v Mariboru, Fakulteta za naravoslovje in matematiko
1 shared publication - Evan Morgan
Pennsylvania State University
1 shared publication
Latest Publications
- Open Access
Unavoidable Induced Subgraph of Infinite 2-connected Graphs
In 1930, Ramsey proved that every infinite graph contains either an infinite clique or an infinite independent set as an induced subgraph. K\"{o}nig proved that every infinite graph contains either a ray or a vertex of infinite degree. In this paper, we establish the 2-connected analog of these results.
Open AccessUnavoidable Induced Subgraph of Infinite 2-connected Graphs
In 1930, Ramsey proved that every infinite graph contains either an infinite clique or an infinite independent set as an induced subgraph. K\"{o}nig proved that every infinite graph contains either a ray or a vertex of infinite degree. In this paper, we establish the 2-connected analog of these results.
- Open Access
Unavoidable Induced Subgraphs of Large 2-Connected Graphs
Ramsey proved that for every positive integer $n$, every sufficiently large graph contains an induced $K_n$ or $\overline{K}_n$. Among the many extensions of Ramsey's Theorem there is an analogue for connected graphs: for every positive integer $n$, every sufficiently large connected graph contains an induced $K_n$, $K_{1,n}$, or $P_n$. In this paper, we establish an analogue for 2-connected graphs. In particular, we prove that for every integer exceeding two, every sufficiently large 2-connected graph contains one of the following as an induced subgraph: $K_n$, a subdivision of $K_{2,n}$, a subdivision of $K_{2,n}$ with an edge between the two vertices of degree $n$, and a well-defined structure similar to a ladder.Open AccessUnavoidable Induced Subgraphs of Large 2-Connected Graphs
Ramsey proved that for every positive integer $n$, every sufficiently large graph contains an induced $K_n$ or $\overline{K}_n$. Among the many extensions of Ramsey's Theorem there is an analogue for connected graphs: for every positive integer $n$, every sufficiently large connected graph contains an induced $K_n$, $K_{1,n}$, or $P_n$. In this paper, we establish an analogue for 2-connected graphs. In particular, we prove that for every integer exceeding two, every sufficiently large 2-connected graph contains one of the following as an induced subgraph: $K_n$, a subdivision of $K_{2,n}$, a subdivision of $K_{2,n}$ with an edge between the two vertices of degree $n$, and a well-defined structure similar to a ladder. - 1 March 2016
- Published by Elsevier in Advances in Applied Mathematics
- Vol. 74, 23-208
Characterizing 2-crossing-critical graphs
- 1 March 2016
- Published by Elsevier in Advances in Applied Mathematics
- Vol. 74, 23-208
Characterizing 2-crossing-critical graphs
- Open Access
- 16 October 2015
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 22 (4) , P4.5
Bounding Tree-Width via Contraction on the Projective Plane and Torus.
If $X$ is a collection of edges in a graph $G$, let $G/X$ denote the contraction of $X$. Following a question of Oxley and a conjecture of Oporowski, we prove that every projective planar graph $G$ admits an edge partition $\{X,Y\}$ such that $G/X$ and $G/Y$ have tree-width at most three. We prove that every toroidal graph $G$ admits an edge partition $\{X,Y\}$ such that $G/X$ and $G/Y$ have tree-width at most three and four, respectively.- 16 October 2015
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 22 (4) , P4.5
Open AccessBounding Tree-Width via Contraction on the Projective Plane and Torus.
If $X$ is a collection of edges in a graph $G$, let $G/X$ denote the contraction of $X$. Following a question of Oxley and a conjecture of Oporowski, we prove that every projective planar graph $G$ admits an edge partition $\{X,Y\}$ such that $G/X$ and $G/Y$ have tree-width at most three. We prove that every toroidal graph $G$ admits an edge partition $\{X,Y\}$ such that $G/X$ and $G/Y$ have tree-width at most three and four, respectively. - Open Access
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.Open AccessA 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. - 6 May 2009
- Published by Elsevier in Discrete Mathematics
- Vol. 309 (9) , 2948-2951
Coloring graphs with crossings
- 6 May 2009
- Published by Elsevier in Discrete Mathematics
- Vol. 309 (9) , 2948-2951
Coloring graphs with crossings
- 1 March 2002
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 11 (2) , 191-197
Partitioning Matroids with Only Small Cocircuits
We show that, for every positive integer c*, there is an integer n such that, if M is a matroid whose largest cocircuit has size c*, then E(M) can be partitioned into two sets E1 and E2 such that every connected component of each of M[mid ]E1 and M[mid ]E2 has at most n elements.
- 1 March 2002
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 11 (2) , 191-197
Partitioning Matroids with Only Small Cocircuits
We show that, for every positive integer c*, there is an integer n such that, if M is a matroid whose largest cocircuit has size c*, then E(M) can be partitioned into two sets E1 and E2 such that every connected component of each of M[mid ]E1 and M[mid ]E2 has at most n elements.
- 1 January 1999
- Published by Elsevier in Discrete Mathematics
- Vol. 195 (1-3) , 203-227
Minor-equivalence for infinite graphs
- 1 January 1999
- Published by Elsevier in Discrete Mathematics
- Vol. 195 (1-3) , 203-227
Minor-equivalence for infinite graphs
- 1 January 1998
- Published by Springer Nature in Combinatorica
- Vol. 18 (1) , 1-12
Partitioning Graphs of Bounded Tree-Width
- 1 January 1998
- Published by Springer Nature in Combinatorica
- Vol. 18 (1) , 1-12
Partitioning Graphs of Bounded Tree-Width