![](/files/happy5.png)
coloring
Reed's omega, delta, and chi conjecture ★★★
Author(s): Reed
For a graph , we define
to be the maximum degree,
to be the size of the largest clique subgraph, and
to be the chromatic number of
.
Conjecture
for every graph
.
![$ \chi(G) \le \ceil{\frac{1}{2}(\Delta(G)+1) + \frac{1}{2}\omega(G)} $](/files/tex/e499e4dc61f5e76d5be51a2064d6e000a8c82f30.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
Keywords: coloring
Grunbaum's Conjecture ★★★
Author(s): Grunbaum
Conjecture If
is a simple loopless triangulation of an orientable surface, then the dual of
is 3-edge-colorable.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
Linial-Berge path partition duality ★★★
Conjecture The minimum
-norm of a path partition on a directed graph
is no more than the maximal size of an induced
-colorable subgraph.
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ D $](/files/tex/b8653a25aff72e3dacd3642492c24c2241f0058c.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
Keywords: coloring; directed path; partition
![Syndicate content Syndicate content](/misc/feed.png)