Consider the following problem:
Problem 4.4.1. Vertex Colouring.
Show that the Stable Set problem reduces to the Vertex Colouring problem.
Hint: For an instance
\((G,k)\) of the Stable Set Problem construct, in polynomial time, a graph
\(H\) and an integer
\(\ell\) (which may differ from
\(k\)) such that
\(G\) has a stable set of cardinality
\(k\) if and only if
\(\chi(H)\leq \ell\text{.}\)
Come up with an algorithm for computing the chromatic number of a graph in time \(O(n^2\cdot n!)\text{.}\)
Given a graph \(H\text{,}\) define the Mycielskian of \(H\) to be the graph \(M(H)\) obtained from \(H\) by adding, for each \(v\in V(H)\text{,}\) a clone vertex \(v'\) adjacent to every neighbour of \(v\) in \(H\) (but not to \(v\)) and a vertex \(v^*\) that is adjacent to all of the clones. Prove that \(\chi(M(H))=\chi(H)+1\) and that, if \(H\) is triangle-free, then so is \(M(H)\text{.}\) Conclude that there are triangle-free graphs of arbitrarily large chromatic number.
Prove that every graph \(G\) satisfies \(\chi(G)\leq \Delta(G)+1\text{.}\)
A matching \(M\) in a graph \(G\) is induced if there does not exist distinct edges \(uv,xy\in M\) where \(uy\in E(G)\text{.}\) Prove that, for every graph \(G\text{,}\) it is possible to colour \(E(G)\) with at most \(2\Delta(G)(\Delta(G)-1)+1\) colours so that the edges of each colour are an induced matching.
Prove that the complement of any odd cycle of length at least \(5\) is not perfect. Do not use the Weak or Strong Perfect Graph Theorems.
-
A co-graph is a graph \(G\) such that there does not exist \(S\subseteq V(G)\) such that \(G[S]\) is equal to a \(4\)-vertex path graph.
Prove that if \(G\) is a co-graph, then either \(G\) or \(\overline{G}\) is disconnected.
Prove that co-graphs are perfect. Do not use the Strong Perfect Graph Theorem.
A simplicial vertex in a graph \(G\) is a vertex \(v\) such that \(G[N(v)]\) is a clique. A graph is chordal if every induced subgraph of \(G\) contains a simplicial vertex. Prove that every chordal graph is perfect. Do not use the Weak or Strong Perfect Graph Theorems.
An orientation of a graph \(G\) is a directed graph obtained by directing each edge of \(G\) toward one of its endpoints. Prove that \(\chi(G)\leq k\) if and only if there is an orientation of \(G\) without any directed path of length \(k\text{.}\)
Let \(G\) be a graph of chromatic number equal to \(k\) and let \(P\) be a set of vertices such that the distance in \(G\) between any two vertices of \(P\) is at least \(4\text{.}\) Prove that and mapping \(f:P\to\{1,\dots,k+1\}\) (called a precolouring) can be extended to a proper \((k+1)\)-colouring of \(G\text{.}\)
Let \(G\) be a graph of chromatic number \(k\) and let \(f:V(G)\to\{1,\dots,k\}\) be a proper \(k\)-colouring of \(G\text{.}\) Prove that there exists a path \(v_1,v_2,\dots,v_k\) in \(G\) such that \(f(v_i)=i\) for \(1\leq i\leq k\text{.}\) Note that the colouring is fixed and the path should go through the colours in the right order (you’re not allowed to re-name the colours).
Provide a polynomial-time algorithm which, given an input graph \(G\text{,}\) either produces a proper \(2\)-colouring of \(G\) or finds a closed walk of odd length in \(G\text{.}\) (A closed walk is a walk that starts and ends at the same vertex).
Provide a polynomial-time algorithm which, given an input graph \(G\text{,}\) produces a proper colouring using at most \(\Delta(G)+1\) colours.
Provide a polynomial-time algorithm which, given an input graph \(G\) with \(n\) vertices and chromatic number equal to \(3\text{,}\) produces a proper colouring using at most \(100\sqrt{n}\) colours. Note that the input graph \(G\) satisfies \(\chi(G)=3\) but the input does not include a proper \(3\)-colouring of \(G\text{.}\) Hint: Think about the degrees of vertices and how you would colour the neighbourhood of a vertex using a small number of colours.
Roughly explain how a similar strategy could be used to find, in polynomial time, a proper colouring of a graph \(G\) with \(\chi(G)=4\) using \(O(n^c)\) colours for some constant \(0< c< 1\text{.}\) What is the smallest \(c\) that you are able to achieve?
How many colours do you get when you generalize this to a graph \(G\) with \(\chi(G)=k\) for arbitrary \(k\geq3\) (up to a constant factor)?
Let \(G_1\) and \(G_2\) be graphs and, for \(i\in\{1,2\}\text{,}\) let \(C_i\) be a clique in \(G_i\) such that \(|C_1|=|C_2|\text{.}\) Let \(G\) be a graph obtained from \(G_1\) and \(G_2\) by identifying each vertex of \(C_1\) with a vertex of \(C_2\) (i.e. we glue together two graphs on these cliques). Prove that \(\chi(G)=\max\{\chi(G_1),\chi(G_2)\}\text{.}\)
Let \(H\) be the graph obtained from the complete graph \(K_4\) by deleting one edge \(uv\text{.}\) Prove that \(\chi(H)=3\) and that every proper \(3\)-colouring of \(H\) maps \(u\) and \(v\) to the same colour.
Let \(P\) be a graph with vertex set \(\mathbb{R}^2\) where any two vertices are adjacent if and only if they are at Euclidean distance \(1\) from each other. Prove that \(\chi(P)\geq 4\text{.}\)
-
Let \(PP\) be the graph whose vertices are all of the lines through the origin in \(\mathbb{R}^3\) where two vertices are adjacent if and only if they correspond to orthogonal lines (here, \(PP\) stands for “projective plane”).
Provide an explicit colouring to show that \(\chi(PP)\leq 4\text{.}\)
Prove that \(\chi(PP)\geq 4\text{.}\) Hint: Consider the subgraph induced by the lines that are spanned by the non-zero vectors in \(\{-1,0,1\}^3\text{.}\) This graph has \(13\) distinct vertices.
Use Kőnig’s Theorem (
Theorem 3.2.1) and the Weak Perfect Graph Theorem (
Theorem 4.1.3) to give a short proof of Kőnig’s Edge Colouring Theorem (
Theorem 4.2.2). Do not use
Corollary 4.2.3 in your proof.
Hint: Think about the chromatic number and clique number of the complement of the line graph.
Prove that, in any finite poset
\((P,\succeq)\text{,}\) the length of the longest chain is equal to the minimum number of antichains that
\(P\) can be partitioned into (i.e. prove
Theorem 1.1.13).
Hint: Induction. Consider the set of minimal elements of
\(P\text{.}\)
Use the Weak Perfect Graph Theorem and the first part of this question to prove Dilworth’s Theorem (
Theorem 1.1.12).
Hint: Associate each poset to a graph in a natural way (but not a Hasse diagram).
Prove
Lemma 4.2.1.
Hint: It may help to make the graph much larger.
An
edge cover in a graph
\(G\) without isolated vertices is a set of edges that covers every vertex. Let
\(\rho(G)\) be the cardinality of the smallest edge cover. Use
Theorem 4.1.3 to prove that every bipartite graph
\(G\) without isolated vertices satisfies
\(\rho(G)=\alpha(G)\text{.}\)
Prove that, for \(k\geq 1\) and \(n=\binom{2k-1}{k}\text{,}\) we have \(\chi_\ell(K_{n,n})>k\) where \(K_{n,n}\) is the complete bipartite graph in which both parts have \(n\) vertices.
Prove that, if \(G\) is a bipartite graph with \(n\) vertices, then \(\chi_\ell(G)\leq \lfloor \log_2(n)\rfloor+1\text{.}\) Hint: Assign the colours randomly in a smart way and prove an upper bound on the expected number of vertices that do not get coloured.
State and prove a generalization of the result of the previous part of the question to graphs of chromatic number \(k\) for any \(k\geq2\text{.}\)
Suppose that \(G\) is a graph and \(k\) is an integer such that \(\chi_\ell(G)>k\text{.}\) Prove that there exists a list assignment \(L\) for \(G\) such that each list has cardinality \(k\text{,}\) \(G\) is not \(L\)-colourable and
\begin{equation*}
\left|\bigcup_{v\in V(G)}L(v)\right|<|V(G)|.
\end{equation*}
Hint: Suppose \(C:=\bigcup_{v\in V(G)}L(v)\) has cardinality at least \(|V(G)|\text{.}\) Construct a bipartite graph where one side of the bipartition is \(V(G)\text{,}\) the other side is \(C\) and vertex \(v\) is adjacent to colour \(c\) if and only if \(c\in L(v)\text{.}\) Play around with a minimal obstruction to Hall’s Theorem (On which side of the bipartite graph? That’s for you to determine!).
Let \(P_1,\dots,P_k\) be disjoint sets of cardinality \(2\) and let \(K_{2*k}\) be the graph with vertex set \(\bigcup_{i=1}^kP_i\) where the vertices of \(P_i\) are adjacent to the vertices of \(P_j\) if and only if \(i\neq j\text{.}\) In other words, it is a complete \(k\)-partite graph in which every part has size \(2\text{.}\) Prove that \(\chi_{\ell}(K_{2*k})=k\text{.}\)
A digraph is acyclic if it does not contain a directed cycle. Prove that every acyclic digraph has a unique kernel.
A quasikernel in a digraph is a stable set \(Q\) such that every vertex \(v\notin Q\) can reach \(Q\) via a directed path of length at most \(2\text{.}\) Prove that every digraph has a quasikernel.
For each \((i,j)\in \{1,\dots,n\}^2\text{,}\) let \(L(i,j)\) be a set of \(n\) symbols. Prove that there exists a matrix \(A\) such that \(A\) does not contain the same symbol more than once in the same row or more than in the same column and, for all \(1\leq i,j\leq n\text{,}\) the entry of \(A\) on the \(i\)th row and \(j\)th column is an element of \(L(i,j)\text{.}\)
Two players are playing a game. In each round of the game, Player 1 creates a vertex and adds edges from the new vertex to the set of vertices that they already added in previous rounds with the restriction that, at every stage, the graph that they have drawn so far must be a forest (i.e. an acyclic graph or, in other words, a disjoint union of trees), and Player 2 decides on a colour for the new vertex so that the colouring of all vertices added so far is proper. No player can change any decisions that they made on previous rounds. The goal of the first player is to maximize the number of distinct colours that are used and the goal of the second player is to minimize it. Prove that, if both players play optimally, then the number of colours used after \(n\) rounds is \(\lfloor\log_2(n)\rfloor+1\text{.}\)
