# A special case of Vu's conjecture: Coloring nearly disjoint graphs of bounded maximum degree

@article{Kelly2021ASC, title={A special case of Vu's conjecture: Coloring nearly disjoint graphs of bounded maximum degree}, author={Tom Kelly and Daniela K{\"u}hn and Deryk Osthus}, journal={ArXiv}, year={2021}, volume={abs/2109.11438} }

A collection of graphs is nearly disjoint if every pair of them intersects in at most one vertex. We prove that if G1, . . . , Gm are nearly disjoint graphs of maximum degree at most D, then the following holds. For every fixed C, if each vertex v ∈ ⋃m i=1 V (Gi) is contained in at most C of the graphs G1, . . . , Gm, then the (list) chromatic number of ⋃m i=1 Gi is at most D + o(D). This result confirms a special case of a conjecture of Vu and generalizes Kahn’s bound on the list chromatic… Expand

#### 2 Citations

Solution to a problem of Erd\H{o}s on the chromatic index of hypergraphs with bounded codegree

- Mathematics
- 2021

In 1977, Erdős asked the following question: for any integers t, n ∈ N, if G1, . . . , Gn are complete graphs such that each Gi has at most n vertices and every pair of them shares at most t… Expand

Graph and hypergraph colouring via nibble methods: A survey

- Computer Science, Mathematics
- ArXiv
- 2021

A survey of methods, results, and open problems on graph and hypergraph colourings, with a particular emphasis on semi-random ‘nibble’ methods. Expand

#### References

SHOWING 1-10 OF 22 REFERENCES

Asymptotic behavior of the chromatic index for hypergraphs

- Computer Science, Mathematics
- J. Comb. Theory, Ser. A
- 1989

The chromatic index of a Steiner triple-system on n points is asymptotic to n 2, resolving a long-standing conjecture and strengthening and generalizing a result due to Frankl and Rodl concerning the existence of a single almost perfect packing or covering under similar circumstances. Expand

A General Upper Bound on the List Chromatic Number of Locally Sparse Graphs

- Computer Science, Mathematics
- Combinatorics, Probability and Computing
- 2002

Several upper bounds for the strong (list) chromatic index of a graph are derived, under various assumptions, and this result is sharp up to the multiplicative constant K and strengthens previous results by Kim, Johansson, Alon, Krivelevich and Sudakov. Expand

Asymptotically Good List-Colorings

- Mathematics, Computer Science
- J. Comb. Theory, Ser. A
- 1996

The “guided-random” method used in the proof is in the spirit of some earlier work and is thought to be of particular interest, and one simple ingredient is a martingale inequality which ought to prove useful beyond the present context. Expand

Coloring graphs with forbidden bipartite subgraphs

- Mathematics, Computer Science
- ArXiv
- 2021

A conjecture that, for any graph F, there is a constant cF > 0 such that if G is an F -free graph of maximum degree ∆, then χ(G) 6 cF∆/ log ∆ is verified for a class of graphs F that includes all bipartite graphs. Expand

Problems and Results on 3-chromatic Hypergraphs and Some Related Questions

A hypergraphi is a collection of sets. This paper deals with finite hy-pergraphs only. The sets in the hypergraph are called edges, the elements of these edges are points. The degree of a point is… Expand

Asymptotically the List Colouring Constants Are 1

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 2002

In this paper we prove the following result about vertex list colourings, which shows that a conjecture of the first author (1999, J. Graph Theory 31, 149-153) is asymptotically correct. Let G be a… Expand

An average degree condition for independent transversals

- Mathematics
- 2020

In 1994, Erdős, Gyarfas and Łuczak posed the following problem: given disjoint vertex sets $V_1,\dots,V_n$ of size~$k$, with exactly one edge between any pair $V_i,V_j$, how large can $n$ be such… Expand

A Note on Vertex List Colouring

- Mathematics, Computer Science
- Combinatorics, Probability and Computing
- 2001

It is proved that there exists a proper vertex colouring f of G such that f( v) ∈ S(v) for each v ∈ V(G) and this proves a weak version of a conjecture of Reed. Expand

On a list coloring conjecture of Reed

- Computer Science
- J. Graph Theory
- 2002

We construct graphs with lists of available colors for each vertex, such that the size of every list exceeds the maximum vertex-color degree, but there exists no proper coloring from the lists. This… Expand

Palette Sparsification Beyond (Δ+1) Vertex Coloring

- Computer Science, Mathematics
- APPROX-RANDOM
- 2020

This paper proves that sampling Oε(logn) colors per vertex is sufficient for proper coloring of any graph with high probability whenever each vertex is sampling from a list of (1 + ε) · deg(v) arbitrary colors, or even only deg( v) + 1 colors when the lists are the sets of sets of colors. Expand