On well quasi-order of graph classes under homomorphic image orderings

S. Huczynska; N. Ruškuc

doi:10.1016/j.ejc.2017.03.008

On well quasi-order of graph classes under homomorphic image orderings

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper we consider the question of well quasi-order for classes defined by a single obstruction within the classes of all graphs, digraphs and tournaments, under the homomorphic image ordering (in both its standard and strong forms). The homomorphic image ordering was introduced by the authors in a previous paper and corresponds to the existence of a surjective homomorphism between two structures. We obtain complete characterisations in all cases except for graphs under the strong ordering, where some open questions remain.

Original language	English
Pages (from-to)	164-175
Number of pages	12
Journal	European Journal of Combinatorics
Volume	63
Early online date	7 Apr 2017
DOIs	https://doi.org/10.1016/j.ejc.2017.03.008
Publication status	Published - Jun 2017

Access to Document

10.1016/j.ejc.2017.03.008

Huczynska,_2017_HomAv_EJC_AAM
© 2017 Elsevier Ltd. All rights reserved. This work has been made available online in accordance with the publisher’s policies. This is the author created, accepted version manuscript following peer review and may differ slightly from the final published version. The final published version of this work is available at https://doi.org/10.1016/j.ejc.2017.03.008
Accepted author manuscript, 283 KBLicence: CC BY-NC-ND

Cite this

@article{b8747d3b28df4cca844ee811076f335a,

title = "On well quasi-order of graph classes under homomorphic image orderings",

abstract = "In this paper we consider the question of well quasi-order for classes defined by a single obstruction within the classes of all graphs, digraphs and tournaments, under the homomorphic image ordering (in both its standard and strong forms). The homomorphic image ordering was introduced by the authors in a previous paper and corresponds to the existence of a surjective homomorphism between two structures. We obtain complete characterisations in all cases except for graphs under the strong ordering, where some open questions remain.",

author = "S. Huczynska and N. Ru{\v s}kuc",

year = "2017",

month = jun,

doi = "10.1016/j.ejc.2017.03.008",

language = "English",

volume = "63",

pages = "164--175",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press/Elsevier ",

}

TY - JOUR

T1 - On well quasi-order of graph classes under homomorphic image orderings

AU - Huczynska, S.

AU - Ruškuc, N.

PY - 2017/6

Y1 - 2017/6

N2 - In this paper we consider the question of well quasi-order for classes defined by a single obstruction within the classes of all graphs, digraphs and tournaments, under the homomorphic image ordering (in both its standard and strong forms). The homomorphic image ordering was introduced by the authors in a previous paper and corresponds to the existence of a surjective homomorphism between two structures. We obtain complete characterisations in all cases except for graphs under the strong ordering, where some open questions remain.

AB - In this paper we consider the question of well quasi-order for classes defined by a single obstruction within the classes of all graphs, digraphs and tournaments, under the homomorphic image ordering (in both its standard and strong forms). The homomorphic image ordering was introduced by the authors in a previous paper and corresponds to the existence of a surjective homomorphism between two structures. We obtain complete characterisations in all cases except for graphs under the strong ordering, where some open questions remain.

UR - https://arxiv.org/abs/1611.01200

U2 - 10.1016/j.ejc.2017.03.008

DO - 10.1016/j.ejc.2017.03.008

M3 - Article

SN - 0195-6698

VL - 63

SP - 164

EP - 175

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

ER -

On well quasi-order of graph classes under homomorphic image orderings

Abstract

Access to Document

Other files and links

Fingerprint

Sophie Huczynska

Nik Ruskuc

Cite this

On well quasi-order of graph classes under homomorphic image orderings

Abstract

Access to Document

Other files and links

Fingerprint

Profiles

Sophie Huczynska

Nik Ruskuc

Cite this