We show that for every binary matroid $N$ there is a graph $H_*$ such that for the graphic matroid $M_G$ of a graph $G$, there is a matroid-homomorphism from $M_G$ to $N$ if and only if there is a ...graph-homomorphism from $G$ to $H_*$. With this we prove a complexity dichotomy for the problem $\rm{Hom}_\mathbb{M}(N)$ of deciding if a binary matroid $M$ admits a homomorphism to $N$. The problem is polynomial time solvable if $N$ has a loop or has no circuits of odd length, and is otherwise $\rm{NP}$-complete. We also get dichotomies for the list, extension, and retraction versions of the problem.
We show that every generator, in a certain set of generators for the variety of reflexive near unanimity graphs, admits a semilattice polymorphism. We then find a retract of a product of such graphs ...(paths, in fact) that has no semilattice polymorphism. This verifies for reflexive graphs that the variety of graphs with semilattice polymorpisms does not contain the variety of graphs with near-unanimity, or even $3$-ary near-unanimity polymorphisms.
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 L 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 ↦ (L) between the sublattices of and the preorders spanned by a canonical sublattice ⋄ of . We then show that L is a tight sublattice of the product of chains if and only if (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.
In this paper, we present a new proof of the $H$-coloring dichotomy, which was first proved by Hell and Nesetril in 1990, and then was reproved by Bulatov in 2005. Our proof is much shorter than the ...original proof and avoids the algebraic machinery of Bulatov's proof.
Celotno besedilo
Dostopno za:
CEKLJ, DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, UILJ, UKNU, UL, UM, UPUK
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.
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.
Given a graph
H
, let
b
(
H
)
be the minimum integer
b
, if it exists, for which
H
-colouring is
N
P
-complete when restricted to instances with degree bounded by
b
. We show that
b
(
H
)
exists for ...any non-bipartite graph. This verifies for graphs the conjecture of Feder, Hell, and Huang that any
CSP
that is
N
P
-complete, is
N
P
-complete for instances of some maximum degree.
Furthermore, we show the same for all projective
CSP
s, and we get constant upper bounds on the parameter
b
for various infinite classes of graph. For example, we show that
b
(
H
)
=
3
for any graph
H
with girth at least 7 in which every edge lies in a
g
-cycle, where
g
is the odd-girth of
H
.
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.
We consider the maximal size of families of
k
-element subsets of an
n
element set
n
that satisfy the properties that every
r
subsets of the family have non-empty intersection, and no
ℓ
subsets ...contain
n
in their union. We show that for large enough
n
, the largest such family is the trivial one of all
(
n
−
2
k
−
1
)
subsets that contain a given element and do not contain another given element. Moreover we show that unless such a family is such that all subsets contain a given element, or all subsets miss a given element, then it has size at most
.
9
(
n
−
2
k
−
1
)
.
We also obtain versions of these statements for weighted non-uniform families.
PDF
