I. Zaguia

activity

20082026

most citedGraphs containing finite induced paths of unbounded length

3 citations · 5 across the 16 of their papers we have counts for

collaborators

Showing math.COShow all

18 papers · 1 filter

math.CO2025

Cops and Robbers, Clique Covers, and Induced Cycles

Alexander Clow, Imed Zaguia

We consider the Cops and Robbers game played on finite simple graphs. In a graph $G$ , the number of cops required to capture a robber in the Cops and Robbers game is denoted by $c(…

math.CO2024

The structure of interval orders with no infinite antichain

Maurice Pouzet, Imed Zaguia

We prove that if $G = (V, E)$ is a nonprime graph with either no infinite independent set or no infinite clique, then every vertex of $G$ belongs to a maximal strong module distinct f…

math.CO2023

The Aharoni--Korman conjecture for posets whose incomparability graph is locally finite

Imed Zaguia

Aharoni and Korman (Order 9 (1992) 245--253) have conjectured that every ordered set without infinite antichains possesses a chain and a partition into antichains so that each part…

math.CO2022

Minimal prime ages, words and permutation graphs

Djamila Oudrar, Maurice Pouzet, Imed Zaguia

This paper is a contribution to the study of hereditary classes of finite graphs. We classify these classes according to the number of prime structures they contain. We consider su…

math.CO2022

Minimal prime ages, words and permutation graphs Extended abstract

Djamila Oudrar, Maurice Pouzet, Imed Zaguia

This paper is a contribution to the study of hereditary classes of finite graphs. We classify these classes according to the number of prime structures they contain. We consider su…

math.CO2021

Hereditary classes of ordered sets of width at most two

Maurice Pouzet, Imed Zaguia

This paper is a contribution to the study of hereditary classes of relational structures, these classes being quasi-ordered by embeddability. It deals with the specific case of ord…

math.CO2021

Metric properties of incomparability graphs with an emphasis on paths

Maurice Pouzet, Imed Zaguia

We describe some metric properties of incomparability graphs. We consider the problem of the existence of infinite paths, either induced or isometric, in the incomparability graph…

math.CO2021

Permutations Avoiding Certain Partially-ordered Patterns

Kai Ting Keshia Yap, David Wehlau, Imed Zaguia

A permutation $π$ contains a pattern $σ$ if and only if there is a subsequence in $π$ with its letters are in the same relative order as those in $σ$ . Partially ordered patterns (P…

math.CO2020★ 3 cited

Graphs containing finite induced paths of unbounded length

Maurice Pouzet, Imed Zaguia

The age $A (G)$ of a graph $G$ (undirected and without loops) is the collection of finite induced subgraphs of $G$ , considered up to isomorphy and ordered by embeddability…

math.CO2020

Greedy balanced pairs in $N$ -free ordered sets

Imed Zaguia

An $α$ -greedy balanced pair in an ordered set $P = (V, \leq)$ is a pair $(x, y)$ of elements of $V$ such that the proportion of greedy linear extensions of $P$ that put $x$ before $y$ …

math.CO2018

The Aharoni--Korman conjecture for $N$ -free posets with no infinite antichain

Imed Zaguia

We give a necessary and sufficient condition for a $P_{4}$ -free graph to be a cograph. This allows us to obtain a simple proof of the fact that finite $P_{4}$ -free graphs are finite co…

math.CO2017

Interval orders, semiorders and ordered groups

Maurice Pouzet, Imed Zaguia

We prove that the order of an ordered group is an interval order if and only if it is a semiorder. Next, we prove that every semiorder is isomorphic to a collection $J$ of…

math.CO2016★ 1 cited

Iterated Arc Graphs

Danny Rorabaugh, Claude Tardif, David Wehlau +1

The arc graph $δ (G)$ of a digraph $G$ is the digraph with the set of arcs of $G$ as vertex-set, where the arcs of $δ (G)$ join consecutive arcs of $G$ . In 1981, Poljak and Rödl char…

math.CO2016

The 1/3-2/3 Conjecture for ordered sets whose cover graph is a forest

Imed Zaguia

A balanced pair in an ordered set $P = (V, \leq)$ is a pair $(x, y)$ of elements of $V$ such that the proportion of linear extensions of $P$ that put $x$ before $y$ is in the real inte…

math.CO2014★ 1 cited

Pairs of orthogonal countable ordinals

Claude Laflamme, Maurice Pouzet, Nobert Sauer +1

We characterize pairs of orthogonal countable ordinals. Two ordinals $α$ and $β$ are orthogonal if there are two linear orders $A$ and $B$ on the same set $V$ with order types $α$ …

math.CO2011

Some inequalities for orderings of acyclic digraphs

Thomas Bier, Imed Zaguia

Let $D = (V, A)$ be an acyclic digraph. For $x \in V$ define $e_{_{D}} (x)$ to be the difference of the indegree and the outdegree of $x$ . An acyclic ordering of the vertices of $D$ is…

math.CO2011

The 1/3-2/3 conjecture for $N$ -free ordered sets

Imed Zaguia

A balanced pair in a finite ordered set $P = (V, \leq)$ is a pair $(x, y)$ of elements of $V$ such that the proportion of linear extensions of $P$ that put $x$ before $y$ is in the rea…

math.CO2008

On minimal prime graphs and posets

Maurice Pouzet, Imed Zaguia

We show that there are four infinite prime graphs such that every infinite prime graph with no infinite clique embeds one of these graphs. We derive a similar result for infinite p…

Cops and Robbers, Clique Covers, and Induced Cycles

The structure of interval orders with no infinite antichain

The Aharoni--Korman conjecture for posets whose incomparability graph is locally finite

Minimal prime ages, words and permutation graphs

Minimal prime ages, words and permutation graphs Extended abstract

Hereditary classes of ordered sets of width at most two

Metric properties of incomparability graphs with an emphasis on paths

Permutations Avoiding Certain Partially-ordered Patterns

Graphs containing finite induced paths of unbounded length

Greedy balanced pairs in N-free ordered sets

The Aharoni--Korman conjecture for N-free posets with no infinite antichain

Interval orders, semiorders and ordered groups

Iterated Arc Graphs

The 1/3-2/3 Conjecture for ordered sets whose cover graph is a forest

Pairs of orthogonal countable ordinals

Some inequalities for orderings of acyclic digraphs

The 1/3-2/3 conjecture for N-free ordered sets

On minimal prime graphs and posets

Greedy balanced pairs in $N$ -free ordered sets

The Aharoni--Korman conjecture for $N$ -free posets with no infinite antichain

The 1/3-2/3 conjecture for $N$ -free ordered sets