![](/files/happy5.png)
homomorphism
Sidorenko's Conjecture ★★★
Author(s): Sidorenko
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ \left(\frac{2|E(G)|}{|V(G)|^2}\right)^{|E(H)|}|V(G)|^{|V(H)|} $](/files/tex/a6c4d985a1ddfc6c35b74c9ae8e23d64f97d7781.png)
Keywords: density problems; extremal combinatorics; homomorphism
Algorithm for graph homomorphisms ★★
Author(s): Fomin; Heggernes; Kratsch
Is there an algorithm that decides, for input graphs and
, whether there exists a homomorphism from
to
in time
for some constant
?
Keywords: algorithm; Exponential-time algorithm; homomorphism
Hedetniemi's Conjecture ★★★
Author(s): Hedetniemi
![$ G,H $](/files/tex/2f3af3db74643de764bb42fa318d1fed96a2c677.png)
![$ \chi(G \times H) = \min \{ \chi(G), \chi(H) \} $](/files/tex/033af9121dd27ee99677e4e7efbdd3cd19e5612c.png)
Here is the tensor product (also called the direct or categorical product) of
and
.
Keywords: categorical product; coloring; homomorphism; tensor product
Weak pentagon problem ★★
Author(s): Samal
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
Keywords: Clebsch graph; cut-continuous mapping; edge-coloring; homomorphism; pentagon
Mapping planar graphs to odd cycles ★★★
Author(s): Jaeger
![$ \ge 4k $](/files/tex/cf3c6265929d41a26d0297d4ba26c602e0e2d93b.png)
![$ C_{2k+1} $](/files/tex/f20c34c1abcdfc50a63f8c5920f0ddb51a9f7cae.png)
Keywords: girth; homomorphism; planar graph
Pentagon problem ★★★
Author(s): Nesetril
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ g $](/files/tex/4239ee4145983e1d8ad375f0606cc7140bce36a3.png)
![$ g $](/files/tex/4239ee4145983e1d8ad375f0606cc7140bce36a3.png)
![$ G \to C_5 $](/files/tex/090efbbd450a0134afde46b53f2dbe35011946d1.png)
Keywords: cubic; homomorphism
A homomorphism problem for flows ★★
Author(s): DeVos
![$ M,M' $](/files/tex/4bd0590f5618f9306e6f1a2fe10e8b811859c1d9.png)
![$ B \subseteq M $](/files/tex/0841b3f2c65d1f2fa19ef611b62df2cbe21b707b.png)
![$ B' \subseteq M' $](/files/tex/3be253a61ac2430d053b2c331b9d0516305f8116.png)
![$ B=-B $](/files/tex/44dba92dfcc7e25e513f45325ee83a69a896eb1c.png)
![$ B' = -B' $](/files/tex/8fce1069de40506650f70aa0d0ee79f5a36ed456.png)
![$ Cayley(M,B) $](/files/tex/5264bebd8d0c334fec1533103d0f600b665604c2.png)
![$ Cayley(M',B') $](/files/tex/e2d1e39749b1550537591fb4ea1057b69feb5bb0.png)
Keywords: homomorphism; nowhere-zero flow; tension
![Syndicate content Syndicate content](/misc/feed.png)