22
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Distinguishing colorings, proper colorings, and covering properties without the Axiom of Choice

      Preprint
      , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We work with simple graphs in ZF (Zermelo--Fraenkel set theory without the Axiom of Choice (AC)) and cardinals in the absence of AC to prove that the following statements are equivalent to K\H{o}nig 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. Our results strengthen some results of Stawiski from a recent paper on the role of the Axiom of Choice in proper and distinguishing colorings since Stawiski worked with cardinals in the presence of AC. We also 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\H{o}nig 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.

          Related collections

          Author and article information

          Journal
          12 September 2023
          Article
          2309.06116
          049c574c-ceeb-4b86-a910-79983f618083

          http://creativecommons.org/licenses/by/4.0/

          History
          Custom metadata
          03E25 (Primary) 05C63, 05C15, 05C69 (Secondary)
          13 pages, 8 figures, 1 table
          math.CO math.LO

          Combinatorics,Logic & Foundation
          Combinatorics, Logic & Foundation

          Comments

          Comment on this article