Recent questions tagged graph-coloring

Suppose BFS is run on a cycle graph $C_n$. For which values of $n$ will no coloring conflict occur?All $n$ Odd $n$ Even $n$ Only prime $n$

What is the largest number of knights that can be placed on a $60 \times 60$ chessboard such that no two knights attack each other (two knights attack each other if they ...

For any undirected connected graph \( G \), let \( \chi(G) \) be the minimum number of colours needed to colour all the vertices of \( G \) in such a way that no two adja...

​​​​​​The $15$ parts of the given figure are to be painted such that no two adjacent parts with shared boundaries (excluding corners) have the same color. The minimum num...

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is __________.

​​​The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let $G$ be any graph with $n$ vertices and chromatic number $...

Consider the following statements:$\text{P}$: There exists no simple, undirected and connected graph with $80$ vertices and $77$ edges.$\text{Q}$: All vertices of Euler g...

A graph $G=(V, E)$ is said to be $k$-colourable if the set $V$ of vertices can be coloured with $k$ colours such that no edge has both its endpoints of the same colour. I...

You have a regular tetrahedron and $4$ distinct colours. You wish to paint the faces of the tetrahedron such that each face gets a different colour. How many ways can you...

Let $G$ be a simple, finite, undirected graph with vertex set $\left\{v_{1}, \ldots, v_{n}\right\}$. Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N}=...