861 problems

Let $N$ be the network from the hexwheel example, let $m\geq 3$, and write $\operatorname{cp}_m(\lambda)=\operatorname{rcp}(M(N))$. Let $\omega_\pm=\lambda-2\pm\sqrt{\lambda^2+4}$.…

For a graph $G$, let $\chi_{\ell}(G)$ denote its list-chromatic number and let $\chi_{\ell}^*(G)$ denote its list packing number, the least $k$ such that every $k$-assignment admit…

For every integer $n$ and every triangle-free graph $G$ on $n$ vertices, if $\delta(G)>n/3$, then $\chi(G)\le 4$.

For every simple graph $G$, the adjacent vertex distinguishing total chromatic number satisfies $\chi''_{a}(G)\leq \Delta(G)+3$. Here, $\chi''_{a}(G)$ is the least integer $k$ such…

Hedetniemi's conjecture.

Let $t\geq 2$ be fixed, and let $G$ be a $K_{t,t}$-free graph of maximum degree $d$. Let $\chi'_s(G)$ denote its strong chromatic index. Mahdian's conjecture. … The paper proves a…

Linear Arboricity Conjecture. For every simple graph $G$,

Directed Linear Arboricity Conjecture. For every directed graph $D$,

Erdős–Lovász–Tihany Conjecture. If

Let $G$ be a planar graph with maximum degree $\Delta$, and let $\chi_2(G)$ denote the minimum number of colors in a coloring in which vertices at distance at most $2$ receive dist…

All graphs considered are finite, simple, and undirected. For a graph $G$, let $\chi(G)$ denote its chromatic number, $\omega(G)$ its clique number, and $\Delta(G)$ its maximum deg…

Let $G$ be a graph, with maximum degree $\Delta(G)$ and clique number $\omega(G)$. Reed's conjecture. Every graph $G$ satisfies … This refines the Borodin–Kostochka direction and i…

Fox–Grinshpun–Pach conjecture.

Let $G$ be a graph, let $k$ be a positive integer, and let $L$ be a $k$-list assignment for $G$. Write $m:=\left\lceil\frac{|G|}{k}\right\rceil$. An $L$-coloring is $m$-bounded if…

Let $(G,-)$ be the signed graph obtained from a graph $G$ by assigning a negative sign to every edge, and let $(K_t,-)$ be the all-negative signed complete graph. A signed graph mi…

Let $G$ be a planar graph. An odd coloring of $G$ is a proper vertex coloring such that every non-isolated vertex has a color appearing an odd number of times in its neighborhood;…

Caro–Petruševski–Škrekovski conjecture. The proper conflict-free chromatic number satisfies

Let $G$ be a $d$-degenerate graph, and let $R_t(G)$ be the graph whose vertices are the proper $t$-colorings of $G$, with two colorings adjacent when they differ on one vertex. The…

Let $G$ be a finite simple graph, let $f_o(G)$ be the maximum order of an induced subgraph of $G$ whose every vertex has odd degree, and let $\chi(G)$ be the chromatic number of…

Let $H$ be a fixed forest, and let $\mathcal{G}(H)$ denote the hereditary class of graphs with no induced subgraph isomorphic to $H$. A graph class is chi-bound if there is a funct…

Let $G$ be an $(a,b)$-bipartite graph, meaning that the two vertex classes of $G$ have maximum degrees at most $a$ and $b$, respectively. Brualdi–Quinn Massey's conjecture. The str…

Tomescu's ℓ-connected generalization.

For graphs $G$ and $H$, let $G\times H$ denote their categorical product and let $\chi(G)$ denote the chromatic number of a graph. Hedetniemi's conjecture. … This is a famous open…

A planar graph is a graph that can be embedded in the plane. Steinberg's conjecture. Every planar graph with no cycles of length four or five is $3$-colorable. Steinberg's conjectu…

Let $G$ be a graph. A total coloring is a function $g:V\cup E\to\{1,2,\dots,k\}$, with total vertex weight $\sigma^t(v)=g(v)+\sum_{v\in e}g(e)$. Adjacent vertices are distinguished…