Soukup 2015 open problems around uncountable graphs

../

conjecture_1_1: The handout's Conjecture 1.1, credited to Erdős and Hajnal, says that some graph of chromatic number omega_1 has no nonempty infinitely connected subgraph; the handout records the weaker uncountable version as known.

conjecture_2_1: The handout's Conjecture 2.1, credited to Erdős and Hajnal, says that some graph of chromatic number omega_1 has a triangle in every subgraph of uncountable chromatic number; the handout records it as consistent and open in ZFC.

conjecture_3_1: The handout's Conjecture 3.1, credited to Erdős, says that for each increasing f from N to N some uncountably chromatic graph has every n-chromatic subgraph of size at least f(n); the handout records it as consistent and open in ZFC.

conjecture_6_1: The handout's Conjecture 6.1, credited to Erdős and Hajnal, says that every omega_1-chromatic graph has an edge coloring into omega_1 such that every countable partition of the vertices has a class carrying every color.

problem_4_1: The handout's Problem 4.1, credited to Erdős, asks whether every two graphs of chromatic number omega_1 share a 4-chromatic, or an omega-chromatic, subgraph; the handout leaves it open.

---

Daniel T. Soukup, Open problems around uncountable graphs. Workshop handout, University of East Anglia (Independence Results in Mathematics and Challenges in Iterated Forcing, November 2015), 5 pp. No notice is printed in the handout (pp. 1-5 read), and the author's site that hosts it states no copyright, license or terms, its only footer line being "Design by Free Web Page Templates" (https://danieltsoukup.github.io/academic/, read 2026-10-02); the term is unstated.

This short handout collects famous and lesser-known open problems on uncountable graphs, focused on chromatic number, each with a short note on what is known or consistent. Sections cover infinitely connected subgraphs (Conjecture 1.1, Erdos-Hajnal), triangle-free subgraphs (Conjecture 2.1, Erdos-Hajnal), growth of finite subgraphs (Conjecture 3.1, Erdos), common subgraphs (Problems 4.1-4.3), Hajnal-Máté graphs (Problems 5.1-5.2), simultaneous chromatic number (Conjectures 6.1-6.2), smooth graphs (Problems 7.1-7.2), products of graphs (Problem 8.1), unfriendly partitions (Problem 9.1, Cowan-Emerson), girth versus chromatic number (Problem 10.1), and a closing list of other topics. No new theorems are proved; the document is a reference list for a talk. Conjecture 2.1 asks for a graph of chromatic number omega_1 in which every subgraph of uncountable chromatic number contains a triangle; the handout records that this is consistent, citing Komjáth and Shelah (J. Symbolic Logic 1988, its reference [21]), even with K_4 omitted and with or without CH, and that the ZFC question was still open in 2015. The handout does not state or settle the general form of Problem 1175, which asks for some cardinal lambda for each uncountable kappa.

Source: https://danieltsoukup.github.io/academic/norwich_handout.pdf.

Read status. Claims checked: Conjectures 1.1, 2.1, 3.1 and 6.1, Problem 4.1, and the remarks recording their status were read clause by clause on the printed pages (pp. 1-3); the handout contains no proofs.

Bears on. #1067: the handout records, citing Soukup's Trees, ladders and graphs (its reference [29]), a graph of chromatic number omega_1 with no uncountable infinitely connected subgraph, hence none of chromatic number omega_1; the result is that paper's. #1068: Conjecture 1.1, if true, gives a graph of chromatic number omega_1 with no nonempty infinitely connected subgraph, so no countably infinite one; the handout records it as open. #1175: Conjecture 2.1 says that lambda = omega_1 does not work for kappa = omega_1; the handout records it as consistent and open in ZFC, and says nothing about larger lambda. #110: Conjecture 3.1, for graphs of chromatic number exactly omega_1, would give a negative answer; as printed it asks only for uncountable chromatic number, and the handout records it as consistent and open in ZFC in 2015. #62: Problem 4.1 is the problem's question; the handout records it as open. #1176: Conjecture 6.1 is the problem's statement; the handout records that it holds consistently, by Hajnal and Komjáth, and does not say whether ZFC proves it.

Results.

• Conjecture 1.1 (Erdos-Hajnal, p. 1): there is a graph of chromatic number omega_1 with no nonempty infinitely connected subgraph; a graph of chromatic number omega_1 with no uncountable infinitely connected subgraph is known, by the handout's reference [29].
• Conjecture 2.1 (Erdos-Hajnal, p. 1): there is a graph of chromatic number omega_1 in which every subgraph of uncountable chromatic number contains a triangle; consistently true by Komjáth and Shelah ([21]), open in ZFC as of 2015.
• Conjecture 3.1 (Erdos, p. 2): for every increasing f from N to N there is a graph of uncountable chromatic number whose every n-chromatic subgraph has size at least f(n); consistently true by Komjáth and Shelah ([22]), open in ZFC.
• Problem 4.1 (Erdos, p. 2): whether every two graphs of uncountable chromatic number (chromatic number omega_1) have a common (a) 4-chromatic, (b) omega-chromatic subgraph. The handout notes the answer is yes for 3-chromatic subgraphs (a common odd cycle), and that two omega_1-chromatic graphs whose product is countably chromatic make it no for omega_1-chromatic subgraphs.
• Conjecture 6.1 (Erdos-Hajnal, simultaneous chromatic number, pp. 2-3): every omega_1-chromatic graph has an edge coloring c : E -> omega_1 such that for every countable partition of the vertices some class carries all colors; consistently true, adding a single Cohen real suffices, credited to Hajnal-Komjáth, Combinatorica 23(1):89-104 ([8]).

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.