Zobrazeno 1 - 10
of 51
pro vyhledávání: '"Kristina Vušković"'
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
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⟩
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
https://doi.org/10.1016/j.jctb.2017.12.004
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⟩
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
https://doi.org/10.1016/j.jctb.2019.07.003
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⟩
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
https://hal.science/hal-03060185/document
Treewidth is a parameter that emerged from the study of minor closed classes of graphs (i.e. classes closed under vertex and edge deletion, and edge contraction). It in some sense describes the global structure of a graph. Roughly, a graph has treewi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::db8fced0bb23f28a483248e33c827d01
http://arxiv.org/abs/2009.01297
http://arxiv.org/abs/2009.01297
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⟩
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
https://hal.archives-ouvertes.fr/hal-03060182/document
Publikováno v:
Journal of Graph Theory. 91:192-246
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 the class of even-hole-free graphs), appearing both as excluded config
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::21b2eb88ec6eca7da7d368b7a91626e1
https://doi.org/10.1002/jgt.22428
https://doi.org/10.1002/jgt.22428
Publikováno v:
Journal of Graph Theory. 90:591-628
In this paper, we study the class of graphs C defined by excluding the following structures as induced subgraphs: theta, pyramid, 1‐wheel, and 3‐wheel. We describe the structure of graphs in C, and we give a polynomial‐time recognition algorith
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4ec1e93b06bffddd03d5b27339bb5d8f
https://doi.org/10.1002/jgt.22415
https://doi.org/10.1002/jgt.22415
Publikováno v:
Discrete Mathematics. 341:463-473
A graph is even-hole-free if it has no induced even cycles of length 4 or more. A cap is a cycle of length at least 5 with exactly one chord and that chord creates a triangle with the cycle. In this paper, we consider (cap, even hole)-free graphs, an
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3b44bff1eef2ec690dc086a68ad0d74b
https://doi.org/10.1016/j.disc.2017.09.013
https://doi.org/10.1016/j.disc.2017.09.013
Publikováno v:
Electronic Notes in Discrete Mathematics. 62:81-86
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 the class of even-hole-free graphs), appearing both as excluded config
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a6477f1c73de80a0a821ef3464299e61
https://doi.org/10.1016/j.endm.2017.10.015
https://doi.org/10.1016/j.endm.2017.10.015