![](/files/happy5.png)
coloring
Crossing numbers and coloring ★★★
Author(s): Albertson
We let denote the crossing number of a graph
.
![$ 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
Are vertex minor closed classes chi-bounded? ★★
Author(s): Geelen
Keywords: chi-bounded; circle graph; coloring; vertex minor
Graphs with a forbidden induced tree are chi-bounded ★★★
Author(s): Gyarfas
Say that a family of graphs is
-bounded if there exists a function
so that every
satisfies
.
![$ T $](/files/tex/79f55d2e1d83a7726c807a70cbe756713b0437b6.png)
![$ T $](/files/tex/79f55d2e1d83a7726c807a70cbe756713b0437b6.png)
![$ \chi $](/files/tex/0308ad82f7a52e8b5406c475bffba60ea6867b7a.png)
Keywords: chi-bounded; coloring; excluded subgraph; tree
Domination in plane triangulations ★★
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ \le \frac{1}{4} |V(G)| $](/files/tex/5f9f42bc03a1d128f5e02773890a16d24e450a5c.png)
Keywords: coloring; domination; multigrid; planar graph; triangulation
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.
![$ K_n $](/files/tex/3047d5de14f4534bc7c4d3e1d86c3fb292aea727.png)
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
Keywords: coloring; complete graph
Counting 3-colorings of the hex lattice ★★
Author(s): Thomassen
![$ \lim_{n \rightarrow \infty} (\chi( H_n , 3)) ^{ 1 / |V(H_n)| } $](/files/tex/f0a8cb3e30752d801fe1d52a9759cf0e47894c8a.png)
Keywords: coloring; Lieb's Ice Constant; tiling; torus
4-regular 4-chromatic graphs of high girth ★★
Author(s): Grunbaum
Coloring random subgraphs ★★
Author(s): Bukh
If is a graph and
, we let
denote a subgraph of
where each edge of
appears in
with independently with probability
.
![$ c $](/files/tex/dccee841f3f498c2c58fa6ae1c1403c5a88c5b8d.png)
![$ {\mathbb E}(\chi(G_{1/2})) > c \frac{\chi(G)}{\log \chi(G)} $](/files/tex/4b1ef3a1f1774128d4eb54d55c91dc24f252c1e2.png)
Keywords: coloring; random graph
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
Degenerate colorings of planar graphs ★★★
Author(s): Borodin
A graph is
-degenerate if every subgraph of
has a vertex of degree
.
![$ 1 \le k \le 4 $](/files/tex/8444626f9ce5a1ce2947ad77497c0627b390df33.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ (k-1) $](/files/tex/bc98477dfed13603bd35290b8c8d5cd9c5af536f.png)
Keywords: coloring; degenerate; planar
![Syndicate content Syndicate content](/misc/feed.png)