http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
Distributive lattice polymorphisms on reflexive graphs
시거스, 마크 할버 대한수학회 2018 대한수학회보 Vol.55 No.1
In this paper we give two characterisations of the class of reflexive graphs admitting {\em 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.
Towards A Dichotomy for the List Switch Homomorphism Problem for Signed Graph
김효빈,시거스, 마크 할버 경북대학교 자연과학대학 수학과 2023 Kyungpook mathematical journal Vol.63 No.3
We make advances towards a structural characterisation of the signed graphs H for which the list switch H-colouring problem List-S-Hom(H) can be solved in polynomial time. We conjecture two different characterisations, the second refining the first, in the case that the graph H can be switched to a graph in which every negative edge is also positive. Using a recent proof of the first characterisations for reflexive signed graphs, by Bok et. al., we prove the second characterisation for reflexive signed graphs. We also provide several tools for reducing the problem to the bipartite case, and prove a full complexity dichotomy for a related problem.