0
$\begingroup$

Starting point. Consider the "$V$-graph" on the vertex set $\{1,2,3\}$ and let the edges be $\{1,2\}$ and $\{2,3\}$. This graph is clearly bipartite. It is a trivial observation that whenever we color the $V$-graph with two colors, the vertices $1$ and $3$ receive the same color.

Generalization. If $n\in\mathbb{N}$ is a positive integer, by $[n]$ we denote the set $\{1,\ldots,n\}$. Let $G=(V,E)$ be a finite, simple, undirected graph. If $v\neq w \in V$ we say that $v,w$ are a forced monochromatic pair if the following holds:

Whenever $c:V\to [\chi(G)]$ is a coloring, then $c(v) = c(w)$.

Question. Is there for every positive integer $n$ a graph with a forced monochromatic pair and chromatic number $n$?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Take an edge-critical graph and remove any edge. $\endgroup$
    – Ilya Bogdanov
    Commented Sep 10 at 13:59
  • 1
    $\begingroup$ A complete $n$-partite graph $K_{r_1,r_2,r_3,\dots,r_n}$ where $r_1r_2r_3\cdots r_n\ge2$. $\endgroup$
    – bof
    Commented Sep 12 at 3:56

1 Answer 1

Reset to default
3
$\begingroup$

Yes. Take the complete graph on $n+1$ vertices and delete one edge.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ More generally, take any graph with chromatic number $n$ and add a vertex with edges to all but one of the existing vertices. $\endgroup$
    – Peter Taylor
    Commented Sep 10 at 16:32
  • 1
    $\begingroup$ The generalization is too general, e.g., if $n=2$ and you start with the graph $P_3$ and join the new vertex to the central vertex and one end-vertex of $P_3$. The chromatic number increases to $3$ and there is no "forced monochromatic pair." $\endgroup$
    – bof
    Commented Sep 11 at 7:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .