![](/files/happy5.png)
chromatic number
Cycles in Graphs of Large Chromatic Number ★★
Author(s): Brewster; McGuinness; Moore; Noel
Conjecture If
, then
contains at least
cycles of length
.
![$ \chi(G)>k $](/files/tex/84d787e716a616f1d9b6d33aea0d9f0777cb1df3.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ \frac{(k+1)(k-1)!}{2} $](/files/tex/2576c24e6815c0bf97ab23f18ad24cf5421aeac4.png)
![$ 0\bmod k $](/files/tex/ef4d29155ecd56ddbfea81561d000d0e5823edb7.png)
Keywords: chromatic number; cycles
Erdős–Faber–Lovász conjecture ★★★
Author(s): Erdos; Faber; Lovasz
Conjecture If
is a simple graph which is the union of
pairwise edge-disjoint complete graphs, each of which has
vertices, then the chromatic number of
is
.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
Keywords: chromatic number
Choosability of Graph Powers ★★
Author(s): Noel
Question (Noel, 2013) Does there exist a function
such that for every graph
,
![$ f(k)=o(k^2) $](/files/tex/bd642e5dd66f1577cedf5fed57f75187a80168ac.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![\[\text{ch}\left(G^2\right)\leq f\left(\chi\left(G^2\right)\right)?\]](/files/tex/989db06683633e86605c26e7d9f0bffc7e46a496.png)
Keywords: choosability; chromatic number; list coloring; square of a graph
Ohba's Conjecture ★★
Author(s): Ohba
Conjecture If
, then
.
![$ |V(G)|\leq 2\chi(G)+1 $](/files/tex/4a7472498fbaf9edea55531f6e3927a3336b2285.png)
![$ \chi_\ell(G)=\chi(G) $](/files/tex/0a2573f7d1a57016f919f018635cd3f9f9875fc4.png)
Keywords: choosability; chromatic number; complete multipartite graph; list coloring
Bounding the chromatic number of triangle-free graphs with fixed maximum degree ★★
Conjecture A triangle-free graph with maximum degree
has chromatic number at most
.
![$ \Delta $](/files/tex/e3f8e135c571143e94f1d4f236326b862080b200.png)
![$ \ceil{\frac{\Delta}{2}}+2 $](/files/tex/522a3a86b51cce46cfcff77891e669d1b9ff9147.png)
Keywords: chromatic number; girth; maximum degree; triangle free
![Syndicate content Syndicate content](/misc/feed.png)