Search Results

As requested by Jukka Kohonen, I'll turn my comment into an answer. The answer is in general no. If such an embedding exists, then the red subgraph and blue subgraph are both planar. However, every …

For an upperbound, the clique number of a $k$-critical graph is obviously at most $k$, and this is achieved by the complete graph $K_k$. There is no non-trivial lowerbound for the clique number, and …

I do not think the bound can be improved without further assumptions. For example, consider the family $\mathcal{F}$ consisting of all singleton subsets of $\{1, \dots, n-1\}$ together with $\{1, \do …

Here is a short proof. Thanks to David Speyer for simplifying an earlier proof of mine (see the comments below). For each colour $i \in [n]$, let $a_i$ be the number of vertices incident to an edge of …

Yes, there are many explicit constructions, although some of them are rather complicated. See this talk of Noga Alon, where he presents a very comprehensive history of the problem. Probably the simp …

Yes, for all $n$, the edge-chromatic number of $K_{2n}$ is $2n-1$ and the edge-chromatic number of $K_{2n+1}$ is $2n+1$. Moreover, it is easy to construct such edge-colourings in polynomial time. Fo …

Here are some observations that are slightly too long for a comment. First, note that the claim is false if we replace $5$ by $4$. Claim. There exists a graph $G$ with $\chi(G)=4$ such that $G$ does …

Let $G$ and $H$ be $k$-critical graphs and $G +_h H$ be the Hajós construction applied to $G$ and $H$ with respect to $vw \in E(G)$ and $xy \in E(H)$. Since $G$ and $H$ are $k$-critical, $G-vw$ and $ …

As mentioned in Grunbaum's paper, this is a conjecture of Erdős from 1964. It was solved completely by Hajnal and Szemerédi in 1970 and is now known as the Hajnal-Szemerédi theorem. A simpler proof …

No, this is false already for $k=3$. Let $A$ and $B$ be disjoint sets of size $n$, and let $H$ be the hypergraph with vertex set $A \cup B$, whose hyperedges are all $3$-subsets $e$ of $A \cup B$ suc …

The Berge-Fulkerson conjecture holds for planar graphs. Here is a proof. Let $G$ be a bridgeless cubic planar graph. The dual graph $G^*$ is a triangulation. By the Four Colour Theorem, $G^*$ has a …

You can get a slightly better upperbound than $\overrightarrow{\chi_{u}} (G)\leq 2^{\Delta(G)}$ by using sets of integers with distinct subset sums. For example, Bohman constructed a set $S$ of $n$ …

Here is how to reduce the problem to a finite colouring problem. Let $G'=G_0 \cup \dots \cup G_K$. For each $t \in \mathbb{N}$, the $tG'$ be the subgraph of $G^\infty$ consisting of $t$ consecutive co …

I strongly suspect that this is NP-complete, but the approach I have in mind does not seem to work! I wanted to use the the well-known fact that it is NP-complete to decide whether the chromatic inde …

For a graph $G$, the $t$-th power of $G$ is the graph $G^t$ with the same vertex set as $G$ and where two vertices are adjacent in $G^t$ if they are connected by a path with at most $t$ edges in $G$. …