List coloring triangle-free hypergraphs
From MaRDI portal
Abstract: A triangle in a hypergraph is a collection of distinct vertices u,v,w and distinct edges e,f,g with u,v in e, v,w in f, w,u in g, and {u,v,w} cap e cap f cap g=emptyset. The i-degree of a vertex in a hypergraph is the number of edges of size i containing it. We prove that every triangle-free hypergraph of rank three (edges have size two or three) with maximum 3-degree Delta_3 and maximum 2-degree Delta_2 has list chromatic number at most c max{Delta_2/ log{Delta_2}}, (Delta_3 / log{Delta_3})^(1/2)} for some absolute positive constant c. This generalizes a result of Johansson and a result of Frieze and the second author.
Recommendations
- List coloring triangle-free planar graphs
- List coloring hypergraphs
- List Colouring Constants of Triangle Free Graphs
- Multiple list colouring triangle free planar graphs
- Coloring triangle-free graphs with local list sizes
- List-colourings of graphs
- List colourings of regular hypergraphs
- List colorings of multipartite hypergraphs
- scientific article; zbMATH DE number 2204176
- scientific article; zbMATH DE number 5531976
Cites work
- A note on embedding hypertrees
- A note on Ramsey numbers
- Coloring H-free hypergraphs
- Coloring graphs with sparse neighborhoods
- Concentration of Measure for the Analysis of Randomized Algorithms
- scientific article; zbMATH DE number 854567 (Why is no real title available?)
- Hypergraph Ramsey numbers: triangles versus cliques
- Models and thresholds for random constraint satisfaction problems
- On Brooks' Theorem for Sparse Graphs
- On the independence number of sparse graphs
- On Turan's theorem for sparse graphs
- Probability Inequalities for Sums of Bounded Random Variables
- Randomly coloring simple hypergraphs
- Sparse hypergraphs with low independence number
- The Ramsey number R(3, t) has order of magnitude t2/log t
Cited in
(10)- Sparse hypergraphs with low independence number
- Triangle-free subgraphs of hypergraphs
- Hypergraph Ramsey numbers: triangles versus cliques
- Coloring sparse hypergraphs
- The -Ramsey problem for triangle-free graphs
- Graph and hypergraph colouring via nibble methods: a survey
- Defective coloring of hypergraphs
- Applications of sparse hypergraph colorings
- Chromatic Ramsey number of acyclic hypergraphs
- Combinatorics. Abstracts from the workshop held January 4--9, 2026
This page was built for publication: List coloring triangle-free hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452728)
