ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P4.06
https://doi.org/10.26493/1855-3974.3233.185
(Also available at http://amc-journal.eu)
Distinguishing colorings, proper colorings, and
covering properties without AC*
Amitayu Banerjee †
Alfréd Rényi Institute of Mathematics, Reáltanoda utca 13-15, 1053, Budapest, Hungary
Zalán Molnár ‡ , Alexa Gopaulsingh
Eötvös Loránd University, Department of Logic, Múzeum krt. 4, 1088, Budapest, Hungary
Received 24 September 2023, accepted 20 March 2024, published online 26 September 2024
Abstract
We work with simple graphs in ZF (i.e., the Zermelo–Fraenkel set theory without the
Axiom of Choice (AC)) and assume that the sets of colors can be either well-orderable
or non-well-orderable, to prove that the following statements are equivalent to Kőnig’s
Lemma:
(a) Any infinite locally finite connected graph G such that the minimum degree of G is
greater than k, has a chromatic number for any fixed integer k greater than or equal
to 2.
(b) Any infinite locally finite connected graph has a chromatic index.
(c) Any infinite locally finite connected graph has a distinguishing number.
(d) Any infinite locally finite connected graph has a distinguishing index.
The above results strengthen some recent results of Stawiski since he assumed that the sets
of colors can be well-ordered. We formulate new conditions for the existence of irreducible
proper coloring, minimal edge cover, maximal matching, and minimal dominating set in
connected bipartite graphs and locally finite connected graphs, which are either equivalent
to AC or Kőnig’s Lemma. Moreover, we show that if the Axiom of Choice for families of
2-element sets holds, then the Shelah-Soifer graph has a minimal dominating set.
*The authors are very thankful to the three anonymous referees for reading the manuscript in detail and for
providing several comments and suggestions that improved the quality and the exposition of the paper.
†Corresponding author.
‡Supported by the ÚNKP-23-3 New National Excellence Program of the Ministry of Culture and Innovation
from the source of the national research, development and innovation fund.
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
Keywords: Axiom of Choice, proper colorings, distinguishing colorings, minimal edge cover, maximal
matching, minimal dominating set.
Math. Subj. Class. (2020): Primary 03E25; Secondary 05C63, 05C15, 05C69
E-mail addresses: banerjee.amitayu@gmail.com (Amitayu Banerjee), mozaag@gmail.com (Zalán Molnár),
alexa279e@gmail.com (Alexa Gopaulsingh)
ISSN 1855-3966 (tiskana izd.), ISSN 1855-3974 (elektronska izd.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P4.06
https://doi.org/10.26493/1855-3974.3233.185
(Dostopno tudi na http://amc-journal.eu)
Razlikovalna barvanja, pravilna barvanja in
lastnosti pokritij brez aksioma izbire*
Amitayu Banerjee †
Alfréd Rényi Institute of Mathematics, Reáltanoda utca 13-15, 1053, Budapest, Hungary
Zalán Molnár ‡ , Alexa Gopaulsingh
Eötvös Loránd University, Department of Logic, Múzeum krt. 4, 1088, Budapest, Hungary
Prejeto 24. septembra 2023, sprejeto 20. marca 2024, objavljeno na spletu 26. septembra 2024
Povzetek
Obravnavamo enostavne grafe v okviru ZF (tj. Zermelo–Fraenklove teorije množic
brez aksioma izbire) in predpostavljamo, da se da množico barv bodisi dobro urediti bodisi
ne, zato da dokažemo, da so naslednje trditve, ekvivalentne Kőnigovi lemi:
(a) Vsak neskončen lokalno končen povezan graf G, za katerega je minimalna stopnja
njegovih točk večja od k, ima kromatsko število za katerokoli fiksno celo število k
večje ali enako 2.
(b) Vsak neskončen lokalno končen povezan graf ima kromatski indeks.
(c) Vsak neskončen lokalno končen povezan graf ima razlikovalno število.
(d) Vsak neskončen lokalno končen povezan graf ima razlikovalni indeks.
Zgornji rezultati izboljšujejo nekaj nedavnih rezultatov Stawiskega, saj je on predpostavil,
da se da množico barv dobro urediti. Oblikujemo nove pogoje za obstoj nereducibilnega
pravilnega barvanja, minimalnega pokritja povezav, maksimalnega prirejanja in minimalne
dominacijske množice v povezanih dvodelnih grafih in lokalno končnih povezanih grafih,
ki so ekvivalentni bodisi aksiomu izbire bodisi Kőnigovi lemi. Pokažemo tudi, da če ak-
siom izbire velja za družine 2-elementnih množic, potem ima Shelah-Soiferjev graf mini-
malno dominacijsko množico.
*Avtorji se zahvaljujejo trem anonimnim recenzentom za podrobno branje rokopisa in številne pripombe in
predloge, ki so izboljšali kakovost in razumljivost članka.
†Kontaktni avtor.
‡Podprt s strani programa ÚNKP-23-3 Nova nacionalna odličnost Ministrstva za kulturo in inovacije iz vira
nacionalnega sklada za raziskave, razvoj in inovacije.
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/
Ključne besede: Aksiom izbire, pravilna barvanja, razlikovalna barvanja, minimalno pokritje povezav,
maksimalno prirejanje, minimalna dominacijska množica.
Math. Subj. Class. (2020): Primarna 03E25; Sekundarna 05C63, 05C15, 05C69
E-poštni naslovi: banerjee.amitayu@gmail.com (Amitayu Banerjee), mozaag@gmail.com (Zalán Molnár),
alexa279e@gmail.com (Alexa Gopaulsingh)