![](/files/happy5.png)
coloring
Seagull problem ★★★
Author(s): Seymour
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
![$ 3 $](/files/tex/4aaf85facb6534fd470edd32dbdb4e28f6218190.png)
![$ \ge \frac{n}{2} $](/files/tex/4efffa1e5aca5aa0354077be96157068fab5f8be.png)
Keywords: coloring; complete graph; minor
Coloring squares of hypercubes ★★
Author(s): Wan
If is a simple graph, we let
denote the simple graph with vertex set
and two vertices adjacent if they are distance
in
.
![$ \chi(Q_d^{(2)}) = 2^{ \lfloor \log_2 d \rfloor + 1} $](/files/tex/926a7d4eb7afdf8197ff1121f017d56c061947b8.png)
Unfriendly partitions ★★★
If is a graph, we say that a partition of
is unfriendly if every vertex has at least as many neighbors in the other classes as in its own.
Keywords: coloring; infinite graph; partition
5-coloring graphs with small crossing & clique numbers ★★
For a graph , we let
denote the crossing number of
, and we let
denote the size of the largest complete subgraph of
.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ cr(G) \le 5 $](/files/tex/a403effa182f63b08ce8a87b127d4400b86db161.png)
![$ \omega(G) \le 5 $](/files/tex/2320b0f36ab8acdec343b9d613e16e4bab300f1f.png)
Keywords: coloring; crossing number; planar graph
Coloring the Odd Distance Graph ★★★
Author(s): Rosenfeld
The Odd Distance Graph, denoted , is the graph with vertex set
and two points adjacent if the distance between them is an odd integer.
![$ \chi({\mathcal O}) = \infty $](/files/tex/cb1eb2f7a7c0eacc877dca7708d0e44b2835f0c2.png)
Keywords: coloring; geometric graph; odd distance
Coloring and immersion ★★★
Author(s): Abu-Khzam; Langston
![$ 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
Bounding the chromatic number of graphs with no odd hole ★★★
Author(s): Gyarfas
![$ f : {\mathbb N} \rightarrow {\mathbb N} $](/files/tex/e5839c90f2b5ca6fe2f58de668c9549b3ad831bd.png)
![$ \chi(G) \le f(\omega(G)) $](/files/tex/4ecaa216fb961541a2aa91c99df9d018ca9e5597.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
Keywords: chi-bounded; coloring; induced subgraph; odd hole; perfect graph
5-local-tensions ★★
Author(s): DeVos
![$ c $](/files/tex/dccee841f3f498c2c58fa6ae1c1403c5a88c5b8d.png)
![$ c=4 $](/files/tex/b1faa9584556785b57e447d15d1d2178572c5d90.png)
![$ \ge c $](/files/tex/4955fa317e705797fabe67a986cb7273813cce12.png)
Alon-Saks-Seymour Conjecture ★★★
Author(s): Alon; Saks; Seymour
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ m $](/files/tex/ddaab6dc091926fb1da549195000491cefae85c1.png)
![$ \chi(G) \le m+1 $](/files/tex/0aefe0f752ac272776eec5c61c7d1a1822a3d224.png)
Keywords: coloring; complete bipartite graph; eigenvalues; interlacing
Bounded colorings for planar graphs ★★
Author(s): Alon; Ding; Oporowski; Vertigan
![$ f : {\mathbb N} \rightarrow {\mathbb N} $](/files/tex/e5839c90f2b5ca6fe2f58de668c9549b3ad831bd.png)
![$ d $](/files/tex/aeba4a4076fc495e8b5df04d874f2911a838883a.png)
![$ \{V_1,V_2,V_3\} $](/files/tex/4743659cb13aa2fd42df6291dc9839397a771197.png)
![$ i=1,2,3 $](/files/tex/a551cf18cf10c10840b4155cdb12c330c8fec96b.png)
![$ V_i $](/files/tex/af854be1f03aac481e0a165c3908976d4b5b0aa0.png)
![$ f(d) $](/files/tex/eb1c96d175a846e74b707abbc2eabf3ea4a2d7b2.png)
Keywords: coloring; partition; planar graph
![Syndicate content Syndicate content](/misc/feed.png)