Orientations of graphs with uncountable chromatic number
| Autor: | Dániel T. Soukup |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Mathematics::General Topology
0102 computer and information sciences Orientation (graph theory) 01 natural sciences Combinatorics Computer Science::Discrete Mathematics FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Partition (number theory) Chromatic scale 0101 mathematics Mathematics Mathematics::Combinatorics Conjecture 010102 general mathematics Digraph Mathematics - Logic Girth (graph theory) Mathematics::Logic Arbitrarily large 010201 computation theory & mathematics 05C63 05C20 05C15 05E35 03E35 Uncountable set Combinatorics (math.CO) Geometry and Topology Logic (math.LO) |
| Zdroj: | Journal of Graph Theory. 88:606-630 |
| ISSN: | 0364-9024 |
| Popis: | Motivated by an old conjecture of P. Erd\H{o}s and V. Neumann-Lara, our aim is to investigate digraphs with uncountable dichromatic number and orientations of undirected graphs with uncountable chromatic number. A graph has uncountable chromatic number if its vertices cannot be covered by countably many independent sets, and a digraph has uncountable dichromatic number if its vertices cannot be covered by countably many acyclic sets. We prove that consistently there are digraphs with uncountable dichromatic number and arbitrarily large digirth; this is in surprising contrast with the undirected case: any graph with uncountable chromatic number contains a 4-cycle. Next, we prove that several well known graphs (uncountable complete graphs, certain comparability graphs, and shift graphs) admit orientations with uncountable dichromatic number in ZFC. However, we show that the statement "every graph $G$ of size and chromatic number $\omega_1$ has an orientation $D$ with uncountable dichromatic number" is independent of ZFC. Comment: 25 pages, revised version prepared for publication in the Journal of Graph Theory |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text