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.



Does the existence of a unique chromatic (possibly transfinite) number for every (possibly non-finite) simple graph imply the axiom of choice?
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**](http://dx.doi.org/10.1007/BF02309111), Period. Math. Hung. 22, No.1, 71-75 (1991). [ZBL0748.05056](https://zbmath.org/?q=an:0748.05056).
> 
> 
> 


