Irena Penev

activity

20132023

χ

-Boundedness

29 citations · 75 across the 11 of their papers we have counts for

collaborators

Showing math.COShow all

12 papers · 1 filter

math.CO2023

Bisimplicial separators

Martin Milanič, Irena Penev, Nevena Pivač +1

A minimal separator of a graph $G$ is a set $S \subseteq V (G)$ such that there exist vertices $a, b \in V (G) ∖ S$ with the property that $S$ separates $a$ from $b$ in $G$ , b…

math.CO2019

Coloring rings

Frédéric Maffray, Irena Penev, Kristina Vušković

A ring is a graph $R$ whose vertex set can be partitioned into $k \geq 4$ nonempty sets, $X_{1}, \dots, X_{k}$ , such that for all $i \in {1, \dots, k}$ , the set $X_{i}$ can be ordered as…

math.CO2018

The class of $(P_{7}, C_{4}, C_{5})$ -free graphs: decomposition, algorithms, and $χ$ -boundedness

Kathie Cameron, Shenwei Huang, Irena Penev +1

As usual, $P_{n}$ ( $n \geq 1$ ) denotes the path on $n$ vertices, and $C_{n}$ ( $n \geq 3$ ) denotes the cycle on $n$ vertices. For a family $H$ of graphs, we say that a graph $…

math.CO2017

Clique-cutsets beyond chordal graphs

Valerio Boncompagni, Irena Penev, Kristina Vuskovic

Truemper configurations (thetas, pyramids, prisms, and wheels) have played an important role in the study of complex hereditary graph classes (e.g. the class of perfect graphs and…

math.CO2016★ 1 cited

Stable sets in {ISK4,wheel}-free graphs

Martin Milanič, Irena Penev, Nicolas Trotignon

An ISK4 in a graph G is an induced subgraph of G that is isomorphic to a subdivision of K4 (the complete graph on four vertices). A wheel is a graph that consists of a chordless cy…

math.CO2016

A decomposition theorem for {ISK4,wheel}-free trigraphs

Martin Milanič, Irena Penev, Nicolas Trotignon

An ISK4 in a graph G is an induced subgraph of G that is isomorphic to a subdivision of K4 (the complete graph on four vertices). A wheel is a graph that consists of a chordless cy…

math.CO2015★ 21 cited

Perfect graphs of arbitrarily large clique-chromatic number

Pierre Charbit, Irena Penev, Stéphan Thomassé +1

We prove that there exist perfect graphs of arbitrarily large clique-chromatic number. These graphs can be obtained from cobipartite graphs by repeatedly gluing along cliques. This…

math.CO2014★ 5 cited

Graphs with no induced five-vertex path or antipath

Maria Chudnovsky, Louis Esperet, Laetitia Lemoine +3

We prove that a graph $G$ contains no induced $5$ -vertex path and no induced complement of a $5$ -vertex path if and only if $G$ is obtained from $5$ -cycles and split graphs by repe…

math.CO2014★ 5 cited

Isolating highly connected induced subgraphs

Irena Penev, Stéphan Thomassé, Nicolas Trotignon

We prove that any graph $G$ of minimum degree greater than $2 k^{2} - 1$ has a $(k + 1)$ -connected induced subgraph $H$ such that the number of vertices of $H$ that have neighbors outside…

math.CO2013★ 11 cited

Excluding induced subdivisions of the bull and related graphs

Maria Chudnovsky, Irena Penev, Alexander Scott +1

For any graph $H$ , let $Forb^{*} (H)$ be the class of graphs with no induced subdivision of $H$ . It was conjectured in [A.D. Scott, Induced trees in graphs of large chromatic nu…

math.CO2013★ 29 cited

Substitution and $χ$ -Boundedness

Maria Chudnovsky, Irena Penev, Alex Scott +1

A class $G$ of graphs is said to be {\em $χ$ -bounded} if there is a function $f : N \to R$ such that for all $G \in G$ and all induced s…

math.CO2013★ 3 cited

Excluding four-edge paths and their complements

Maria Chudnovsky, Peter Maceli, Irena Penev

We prove that a graph G contains no induced four-edge path and no induced complement of a four-edge path if and only if G is obtained from five-cycles and split graphs by repeatedl…