Výsledky vyhledávání - "Nicolas Trotignon"

Akademický článek

Autor: Isolde Adler, Ngoc Khang Le, Haiko Müller, Marko Radovanović, Nicolas Trotignon, Kristina Vušković

Publikováno v: Discrete Mathematics & Theoretical Computer Science, Vol Vol. 19 no. 1, Iss Graph Theory (2017)

We present a class of (diamond, even hole)-free graphs with no clique cutset that has unbounded rank-width. In general, even-hole-free graphs have unbounded rank-width, because chordal graphs are even-hole-free. A.A. da Silva, A. Silva and C. Linhare

Externí odkaz: https://doaj.org/article/8241973e88dc4735bcf93f75d9ae78a7

Zobrazit plný text záznamu

The (theta, wheel)-free graphs Part I: Only-prism and only-pyramid graphs

Autor: Marko Radovanović, Nicolas Trotignon, Kristina Vušković, Emilie Diot

Publikováno v: Journal of Combinatorial Theory, Series B
Journal of Combinatorial Theory, Series B, 2020, 143, pp.123-147. ⟨10.1016/j.jctb.2017.12.004⟩
Journal of Combinatorial Theory, Series B, Elsevier, 2020, 143, pp.123-147. ⟨10.1016/j.jctb.2017.12.004⟩

International audience; Truemper configurations are four types of graphs (namely thetas, wheels, prisms and pyramids) that play an important role in the proof of several decomposition theorems for hereditary graph classes. In this paper, we prove two

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::35ca3b3037671fb118d03d38e95dc99c
https://doi.org/10.1016/j.jctb.2017.12.004

Zobrazit plný text záznamu

The (theta, wheel)-free graphs Part III: Cliques, stable sets and coloring

Autor: Marko Radovanović, Kristina Vušković, Nicolas Trotignon

Publikováno v: Journal of Combinatorial Theory, Series B
Journal of Combinatorial Theory, Series B, 2020, 143, pp.185-218. ⟨10.1016/j.jctb.2019.07.003⟩
Journal of Combinatorial Theory, Series B, Elsevier, 2020, 143, pp.185-218. ⟨10.1016/j.jctb.2019.07.003⟩

International audience; A hole in a graph is a chordless cycle of length at least 4. A theta is a graph formed by three paths between the same pair of distinct vertices so that the union of any two of the paths induces a hole. A wheel is a graph form

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f6195d9598fcb08284d452b81bfd0be2
https://doi.org/10.1016/j.jctb.2019.07.003

Zobrazit plný text záznamu

(Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth

Autor: Nicolas Trotignon, Ni Luh Dewi Sintiari, Stéphan Thomassé, Marcin Pilipczuk

Publikováno v: Journal of Graph Theory
Journal of Graph Theory, Wiley, 2021, 97 (4), pp.624-641. ⟨10.1002/jgt.22675⟩
Journal of Graph Theory, 2021, 97 (4), pp.624-641. ⟨10.1002/jgt.22675⟩

International audience; A {\em theta} is a graph made of three internally vertex-disjoint chordless paths $P_1 = a \dots b$, $P_2 = a \dots b$, $P_3 = a \dots b$ of length at least~2 and such that no edges exist between the paths except the three edg

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4ad02ffd4e9bf80fc2c1347bfb2ec433
https://hal.archives-ouvertes.fr/hal-03255160

Zobrazit plný text záznamu

(Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels

Autor: Nicolas Trotignon, Pegah Pournajafi

Publikováno v: Journal of Graph Theory
Journal of Graph Theory, 2021, ⟨10.1002/jgt.22666⟩
Journal of Graph Theory, Wiley, 2021, ⟨10.1002/jgt.22666⟩

The Burling sequence is a sequence of triangle-free graphs of increasing chromatic number. Each of them is isomorphic to the intersection graph of a set of axis-parallel boxes in $R^3$. These graphs were also proved to have other geometrical represen

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4fe92623d323ce285950424b83148a48
https://hal.science/hal-03255154/file/TTF-EHF-Part-1-V3.pdf

Zobrazit plný text záznamu

The (theta, wheel)-free graphs Part IV: Induced paths and cycles

Autor: Nicolas Trotignon, Kristina Vušković, Marko Radovanović

Publikováno v: Journal of Combinatorial Theory, Series B
Journal of Combinatorial Theory, Series B, 2021, 146, pp.495-531. ⟨10.1016/j.jctb.2020.06.002⟩
Journal of Combinatorial Theory, Series B, Elsevier, 2021, 146, pp.495-531. ⟨10.1016/j.jctb.2020.06.002⟩

International audience; A hole in a graph is a chordless cycle of length at least 4. A theta is a graph formed by three internally vertex-disjoint paths of length at least 2 between the same pair of distinct vertices. A wheel is a graph formed by a h

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a760ef213c8975b2e181a64d618913db
https://hal.science/hal-03060185/document

Zobrazit plný text záznamu

On the complexity of colouring antiprismatic graphs

Autor: Nicolas Trotignon, Cléophée Robin, Myriam Preissmann

Publikováno v: Algorithmica
Algorithmica, 2020, 83 (2), pp.589-612. ⟨10.1007/s00453-020-00767-7⟩
Algorithmica, Springer Verlag, 2020, 83 (2), pp.589-612. ⟨10.1007/s00453-020-00767-7⟩

International audience; A graph G is prismatic if for every triangle T of G, every vertex of G not in T has a unique neighbour in T. The complement of a prismatic graph is called \emph{antiprismatic}. The complexity of colouring antiprismatic graphs

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e5e9434a77c0c901bc8e882cb0fa454e
https://hal.science/hal-02392476

Zobrazit plný text záznamu

On the tree-width of even-hole-free graphs

Autor: Pierre Aboulker, Nicolas Trotignon, Eun Jung Kim, Ni Luh Dewi Sintiari, Isolde Adler

Publikováno v: European Journal of Combinatorics
European Journal of Combinatorics, 2021, 98, pp.103394. ⟨10.1016/j.ejc.2021.103394⟩
European Journal of Combinatorics, Elsevier, 2021, 98, pp.103394. ⟨10.1016/j.ejc.2021.103394⟩

The class of all even-hole-free graphs has unbounded tree-width, as it contains all complete graphs. Recently, a class of (even-hole, K 4 )-free graphs was constructed, that still has unbounded tree-width (Sintiari and Trotignon, 2019). The class has

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b6832af357951c74894824fbace99682
http://arxiv.org/abs/2008.05504

Zobrazit plný text záznamu

The (theta, wheel)-free graphs Part II: Structure theorem

Autor: Nicolas Trotignon, Kristina Vušković, Marko Radovanović

Publikováno v: Journal of Combinatorial Theory, Series B
Journal of Combinatorial Theory, Series B, Elsevier, 2020, 143, pp.148-184. ⟨10.1016/j.jctb.2019.07.004⟩
Journal of Combinatorial Theory, Series B, 2020, 143, pp.148-184. ⟨10.1016/j.jctb.2019.07.004⟩

A hole in a graph is a chordless cycle of length at least 4. A theta is a graph formed by three paths between the same pair of distinct vertices so that the union of any two of the paths induces a hole. A wheel is a graph formed by a hole and a node

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bd0fae581cc17e6849a921b8b677a626
https://hal.archives-ouvertes.fr/hal-03060182/document

Zobrazit plný text záznamu

χ-bounds, operations, and chords

Autor: Nicolas Trotignon, Lan Anh Pham

Publikováno v: Journal of Graph Theory
Journal of Graph Theory, Wiley, 2018, 88 (2), pp.312-336. ⟨10.1002/jgt.22214⟩
Journal of Graph Theory, 2018, 88 (2), pp.312-336. ⟨10.1002/jgt.22214⟩

A \emph{long unichord} in a graph is an edge that is the unique chord of some cycle of length at least 5. A graph is \emph{long-unichord-free} if it does not contain any long-unichord. We prove a structure theorem for long-unichord-free graph. We giv

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f9109d9e650a158a9bab76247db55bef
https://doi.org/10.1002/jgt.22214

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání