6
$\begingroup$

Assuming the axiom of choice I can write for any cardinal number $\kappa$ and any simple graph $G$ that a function $f$ is a $\kappa\text{-coloring}$ of $G$ if and only if the cardinality of the image of $f$ is equal to $\kappa$ and that:

$$\forall u,v\in V(G)\left[\{u,v\}\in E(G)\implies f(u)\neq f(v)\right]$$

Now letting $f=\text{id}_{V(G)}$ one sees every simple graph $G$ has a $|V(G)|\text{-coloring}$. Which proves there exists a cardinal number capable of coloring any simple graph, now by the axiom of choice I know that the cardinals are well ordered which means that there must exist a smallest such cardinal that colors any simple graph, thus one can always unambiguously define the chromatic number of a simple graph as the smallest cardinal number which colors it but only if we assume the axiom of choice. So I'm curious if the seemingly stronger converse of this proposition holds, or if not then what can be said on the manner and would really appreciate any references or relevant comments.

$\endgroup$

1 Answer 1

14
$\begingroup$

It seems that your question has a positive answer, as shown by Galvin and Komjáth in their paper

Galvin, F.; Komjáth, P., Graph colorings and the axiom of choice, Period. Math. Hung. 22, No.1, 71-75 (1991). ZBL0748.05056.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.