![](/files/happy5.png)
Vertex coloring
Strong colorability ★★★
Author(s): Aharoni; Alon; Haxell
Let be a positive integer. We say that a graph
is strongly
-colorable if for every partition of the vertices to sets of size at most
there is a proper
-coloring of
in which the vertices in each set of the partition have distinct colors.
![$ \Delta $](/files/tex/e3f8e135c571143e94f1d4f236326b862080b200.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ 2 \Delta $](/files/tex/853908c29bc170f3b27832e4df3751c7626ff012.png)
Keywords: strong 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
.
![$ \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
Circular coloring triangle-free subcubic planar graphs ★★
![$ \frac{20}{7} $](/files/tex/bad459acf1e14f972d8bf6c9f92912e0be945739.png)
Keywords: circular coloring; planar graph; triangle free
Oriented chromatic number of planar graphs ★★
Author(s):
An oriented colouring of an oriented graph is assignment of colours to the vertices such that no two arcs receive ordered pairs of colours
and
. It is equivalent to a homomorphism of the digraph onto some tournament of order
.
Keywords: oriented coloring; oriented graph; planar graph
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
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
Partial List Coloring ★★★
Author(s): Albertson; Grossman; Haas
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
![$ \chi_\ell(G) $](/files/tex/b68082745a25a09294e2c92c006b61d3ef1a9e54.png)
![$ 0\leq t\leq \chi_\ell $](/files/tex/1aee119babfe25de435c7cf6beff3114a5ae9326.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ t $](/files/tex/4761b031c89840e8cd2cda5b53fbc90c308530f3.png)
![$ \frac{tn}{\chi_\ell(G)} $](/files/tex/59b72b19d6799e1fd7a0fc093bff9283068dc838.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
Keywords: list assignment; list coloring
Partial List Coloring ★★★
Author(s): Iradmusa
Let be a simple graph, and for every list assignment
let
be the maximum number of vertices of
which are colorable with respect to
. Define
, where the minimum is taken over all list assignments
with
for all
.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ \chi_\ell $](/files/tex/46e2d5b6cf87b7e24d9ac72345043107b7ccae3a.png)
![$ 1\leq r\leq s\leq \chi_\ell $](/files/tex/a3fc6cd4c98fabb35869474a493492a0435792e7.png)
![\[\frac{\lambda_r}{r}\geq\frac{\lambda_s}{s}.\]](/files/tex/47be18e956355dd433b88b66eabf01a9e3ed5f61.png)
Keywords: list assignment; list coloring
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
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
Circular colouring the orthogonality graph ★★
Author(s): DeVos; Ghebleh; Goddyn; Mohar; Naserasr
Let denote the graph with vertex set consisting of all lines through the origin in
and two vertices adjacent in
if they are perpendicular.
![$ \chi_c({\mathcal O}) = 4 $](/files/tex/ee0ecd597af84da66753671f734858c77288d4be.png)
Keywords: circular coloring; geometric graph; orthogonality
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
Bounding the chromatic number of triangle-free graphs with fixed maximum degree ★★
![$ \Delta $](/files/tex/e3f8e135c571143e94f1d4f236326b862080b200.png)
![$ \ceil{\frac{\Delta}{2}}+2 $](/files/tex/522a3a86b51cce46cfcff77891e669d1b9ff9147.png)
Keywords: chromatic number; girth; maximum degree; triangle free
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
Are vertex minor closed classes chi-bounded? ★★
Author(s): Geelen
Keywords: chi-bounded; circle graph; coloring; vertex minor
Mixing Circular Colourings ★
![$ \mathfrak{M}_c(G) $](/files/tex/f24f4a47b3db2823b31406ff6f37ecb0296f4f10.png)
Keywords: discrete homotopy; graph colourings; mixing
Choice Number of k-Chromatic Graphs of Bounded Order ★★
Author(s): Noel
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ mk $](/files/tex/c6307bea3dbafaf140155114bd35bb788fc000d8.png)
![$ \text{ch}(G)\leq \text{ch}(K_{m*k}) $](/files/tex/0d0a9568608331000410c601a041b1c391b31d01.png)
Keywords: choosability; complete multipartite graph; list coloring
Melnikov's valency-variety problem ★
Author(s): Melnikov
![$ w(G) $](/files/tex/a1ba1262a44dc4c4c585e3e1854ea2218cd40629.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$$\ceil{ \frac{\floor{w(G)/2}}{|V(G)| - w(G)} } ~ ?$$](/files/tex/90d7d0498914cd55d9d67b5608aa716bfcb06880.png)
Keywords:
Earth-Moon Problem ★★
Author(s): Ringel
Keywords:
Acyclic list colouring of planar graphs. ★★★
Author(s): Borodin; Fon-Der-Flasss; Kostochka; Raspaud; Sopena
Keywords:
![Syndicate content Syndicate content](/misc/feed.png)