http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
Five Cycles are Highly Ramsey Infinite
Siggers, Mark Department of Mathematics 2012 Kyungpook mathematical journal Vol.52 No.1
In a previous paper, the author proved that all odd cycles, except five cycles, are highly Ramsey-infinite. In this paper, we fill in the missing case, and show that five cycles are highly Ramsey-infinite.
DISTRIBUTIVE LATTICE POLYMORPHISMS ON REFLEXIVE GRAPHS
Siggers, Mark Korean Mathematical Society 2018 대한수학회보 Vol.55 No.1
In this paper we give two characterisations of the class of reflexive graphs admitting distributive lattice polymorphisms and use these characterisations to address the problem of recognition: we find a polynomial time algorithm to decide if a given reflexive graph G, in which no two vertices have the same neighbourhood, admits a distributive lattice polymorphism.
On the Representations of Finite Distributive Lattices
Siggers, Mark Department of Mathematics 2020 Kyungpook mathematical journal Vol.60 No.1
A simple but elegant result of Rival states that every sublattice L of a finite distributive lattice 𝒫 can be constructed from 𝒫 by removing a particular family 𝒥<sub>L</sub> of its irreducible intervals. Applying this in the case that 𝒫 is a product of a finite set 𝒞 of chains, we get a one-to-one correspondence L ↦ 𝒟<sub>𝒫</sub>(L) between the sublattices of 𝒫 and the preorders spanned by a canonical sublattice 𝒞<sup>⋄</sup> of 𝒫. We then show that L is a tight sublattice of the product of chains 𝒫 if and only if 𝒟<sub>𝒫</sub>(L) is asymmetric. This yields a one-to-one correspondence between the tight sublattices of 𝒫 and the posets spanned by its poset J(𝒫) of non-zero join-irreducible elements. With this we recover and extend, among other classical results, the correspondence derived from results of Birkhoff and Dilworth, between the tight embeddings of a finite distributive lattice L into products of chains, and the chain decompositions of its poset J(L) of non-zero join-irreducible elements.
Non-bipartite pairs of 3-connected graphs are highly Ramsey-infinite
Academic Press 2014 European journal of combinatorics : Journal europ& Vol.36 No.-
A pair of graphs (H<SUB>b</SUB>,H<SUB>r</SUB>) is highly Ramsey-infinite if there is some constant c such that for large enough n there are at least 2<SUP>cn^2</SUP> non-isomorphic graphs on n or fewer vertices that are minimal with respect to the property that when their edges are coloured blue or red, there is necessarily a blue copy of H<SUB>b</SUB> or a red copy of H<SUB>r</SUB>. We show that a pair of 3-connected graphs is highly Ramsey-infinite if and only if at least one of the graphs in non-bipartite. Further we show that the pair (H<SUB>b</SUB>,H<SUB>r</SUB>) is highly Ramsey infinite for H<SUB>r</SUB> an odd cycle of girth @? and H<SUB>b</SUB> any graph with no induced cycle of length @? or longer. In showing the above results, we continue the theory of gadgets called senders and determiners that has been developed over many earlier papers on Ramsey-infinite graphs.
Locally injective k-colourings of planar graphs
Kratochvil, J.,Siggers, M. North Holland ; Elsevier Science Ltd 2014 Discrete Applied Mathematics Vol.173 No.-
A colouring of the vertices of a graph is called injective if every two distinct vertices connected by a path of length 2 receive different colours, and it is called locally injective if it is an injective proper colouring. We show that for k≥4, deciding the existence of a locally injective k-colouring, and of an injective k-colouring, are NP-complete problems even when restricted to planar graphs. It is known that every planar graph of maximum degree @?35k-52 allows a locally injective k-colouring. To compare the behaviour of planar and general graphs we show that for general graphs, deciding the existence of a locally injective k-colouring becomes NP-complete for graphs of maximum degree 2k (when k≥7).
Semilattice polymorphisms and chordal graphs
Hell, P.,Siggers, M. Academic Press 2014 European journal of combinatorics : Journal europ& Vol.36 No.-
We investigate the class of reflexive graphs that admit semilattice polymorphisms, and in doing so, give an algebraic characterisation of chordal graphs. In particular, we show that a graph G is chordal if and only if it has a semilattice polymorphism such that G is a subgraph of the comparability graph of the semilattice. Further, we find a new characterisation of the leafage of a chordal graph in terms of the width of the semilattice polymorphisms it admits. Finally, we introduce obstructions to various types of semilattice polymorphisms, and in doing so, show that the class of reflexive graphs admitting semilattice polymorphisms is not a variety. These are, to our knowledge, the first structural results on graphs with semilattice polymorphisms, beyond the conservative realm.
On the complexity of H-colouring planar graphs
MacGillivray, G.,Siggers, M. North-Holland Pub. Co ; Elsevier Science Ltd 2009 Discrete mathematics Vol.309 No.18
We show that if H is an odd-cycle, or any non-bipartite graph of girth 5 and maximum degree at most 3, then planar H-COL is NP-complete.
Characterisation of forests with trivial game domination numbers
Nadjafi-Arani, M. J.,Siggers, M.,Soltani, H. Springer Science + Business Media 2016 Journal of combinatorial optimization Vol.32 No.3
<P>In the domination game, two players, the Dominator and Staller, take turns adding vertices of a fixed graph to a set, at each turn increasing the number of vertices dominated by the set, until the final set dominates the whole graph. The Dominator plays to minimise the size of the set while the Staller plays to maximise it. A graph is -trivial if when the Dominator plays first and both players play optimally, the set is a minimum dominating set of the graph. A graph is -trivial if the same is true when the Staller plays first. We consider the problem of characterising -trivial and -trivial graphs. We give complete characterisations of -trivial forests and of -trivial forests. We also show that -connected -trivial graphs cannot have large girth, and conjecture that the same holds without the connectivity condition.</P>
Note on robust critical graphs with large odd girth
Nstase, E.,Rodl, V.,Siggers, M. North-Holland Pub. Co ; Elsevier Science Ltd 2010 Discrete mathematics Vol.310 No.3
A graph G is (k+1)-critical if it is not k-colourable but G-e is k-colourable for any edge e@?E(G). In this paper we show that for any integers k>=3 and l>=5 there exists a constant c=c(k,l)>0, such that for all n@?, there exists a (k+1)-critical graph G on n vertices with n>n@? and odd girth at least @?, which can be made (k-1)-colourable only by the omission of at least cn<SUP>2</SUP> edges.
A complexity dichotomy for signed H -colouring
Brewster, Richard C.,Siggers, Mark North-Holland Pub. Co 2018 Discrete mathematics Vol.341 No.10
<P><B>Abstract</B></P> <P>Verifying a conjecture of Brewster, Foucaud, Hell and Naserasr, we show that signed ( H , Π ) -colouring is NP-complete for any signed graph ( H , Π ) whose s-core has at least 3 edges.</P>