Coloring Graphs with Dense Neighborhoods

DOI10.1002/jgt.21768zbMath1304.05052arXiv1209.3646OpenAlexW2592868433MaRDI QIDQ5495890

Landon Rabern

Publication date: 7 August 2014

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1209.3646

zbMATH Keywords

coloringBrooks' theoremReed's conjectureBorodin-Kostochka conjecturedense neighbourhoods

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Vertex degrees (05C07) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Density (toughness, etc.) (05C42)

Related Items (5)

Graphs with $\chi=\Delta$ Have Big Cliques ⋮ Special issue in honour of Landon Rabern ⋮ New bounds for the Moser‐Tardos distribution ⋮ Beyond Ohba's conjecture: a bound on the choice number of \(k\)-chromatic graphs with \(n\) vertices ⋮ Chromatic-choosability of hypergraphs with high chromatic number

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• List colouring when the chromatic number is close to the order of the graph
• Extremal problems for transversals in graphs with bounded degree
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• A strengthening of Brooks' theorem
• On the choosability of complete multipartite graphs with part size three
• Independent systems of representatives in weighted graphs
• Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
• On Forming Committees
• Odd Independent Transversals are Odd
• On the Strong Chromatic Number
• Hitting all maximum cliques with a stable set using lopsided independent transversals
• Coloring Claw-Free Graphs with $\Delta-1$ Colors
• Graph colouring and the probabilistic method

This page was built for publication: Coloring Graphs with Dense Neighborhoods