![](/files/happy5.png)
complete graph
Star chromatic index of complete graphs ★★
Author(s): Dvorak; Mohar; Samal
Conjecture Is it possible to color edges of the complete graph
using
colors, so that the coloring is proper and no 4-cycle and no 4-edge path is using only two colors?
![$ K_n $](/files/tex/3047d5de14f4534bc7c4d3e1d86c3fb292aea727.png)
![$ O(n) $](/files/tex/ee18510ab4140627d7a8df7949d309533b39ebca.png)
Equivalently: is the star chromatic index of linear in
?
Keywords: complete graph; edge coloring; star coloring
Crossing numbers and coloring ★★★
Author(s): Albertson
We let denote the crossing number of a graph
.
Conjecture Every graph
with
satisfies
.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ \chi(G) \ge t $](/files/tex/cb74f630a3b502fe0bd0726e72880c005ec02d22.png)
![$ cr(G) \ge cr(K_t) $](/files/tex/64703b245f27999c87b0a8e3c56c14e80f1925d4.png)
Keywords: coloring; complete graph; crossing number
Double-critical graph conjecture ★★
A connected simple graph is called double-critical, if removing any pair of adjacent vertexes lowers the chromatic number by two.
Conjecture
is the only
-chromatic double-critical graph
![$ K_n $](/files/tex/3047d5de14f4534bc7c4d3e1d86c3fb292aea727.png)
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
Keywords: coloring; complete graph
Seagull problem ★★★
Author(s): Seymour
Conjecture Every
vertex graph with no independent set of size
has a complete graph on
vertices as a minor.
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
![$ 3 $](/files/tex/4aaf85facb6534fd470edd32dbdb4e28f6218190.png)
![$ \ge \frac{n}{2} $](/files/tex/4efffa1e5aca5aa0354077be96157068fab5f8be.png)
Keywords: coloring; complete graph; minor
Coloring and immersion ★★★
Author(s): Abu-Khzam; Langston
Conjecture For every positive integer
, every (loopless) graph
with
immerses
.
![$ t $](/files/tex/4761b031c89840e8cd2cda5b53fbc90c308530f3.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ \chi(G) \ge t $](/files/tex/cb74f630a3b502fe0bd0726e72880c005ec02d22.png)
![$ K_t $](/files/tex/7a86d3ef1cad6ecf4b2ce1338d254d4b623a47d1.png)
Keywords: coloring; complete graph; immersion
The Crossing Number of the Complete Graph ★★★
Author(s):
The crossing number of
is the minimum number of crossings in all drawings of
in the plane.
Conjecture
![$ \displaystyle cr(K_n) = \frac 14 \floor{\frac n2} \floor{\frac{n-1}2} \floor{\frac{n-2}2} \floor{\frac{n-3}2} $](/files/tex/ebb1eaf4332defb7fcc42f4cd3f4fcfc7a0138e7.png)
Keywords: complete graph; crossing number
![Syndicate content Syndicate content](/misc/feed.png)