Colouring graphs with sparse neighbourhoods: bounds and applications

DOI10.1016/j.jctb.2022.01.009zbMath1492.05041arXiv1810.06704OpenAlexW2897904393MaRDI QIDQ2131867

Luke Postle, Marthe Bonamy, Thomas J. Perrett

Publication date: 27 April 2022

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

graph coloringprobabilistic methodstrong chromatic indexReed's conjecture

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Combinatorial aspects of packing and covering (05B40)

Related Items (18)

Colouring graphs with forbidden bipartite subgraphs ⋮ Between Proper and Strong Edge-Colorings of Subcubic Graphs ⋮ Bounding \(\chi\) by a fraction of \(\Delta\) for graphs without large cliques ⋮ Strong chromatic index of graphs with maximum degree four ⋮ List strong edge-coloring of graphs with maximum degree 4 ⋮ Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth ⋮ Strong list-chromatic index of planar graphs with Ore-degree at most seven ⋮ A proof of the Erdős-Faber-Lovász conjecture ⋮ Strong edge-coloring of 2-degenerate graphs ⋮ The tight bound for the strong chromatic indices of claw-free subcubic graphs ⋮ A note on strong edge-coloring of claw-free cubic graphs ⋮ Proper edge-colorings with a rich neighbor requirement ⋮ 子立方平面图的$(1,0)$-松弛强边列表染色 ⋮ Hypergraph incidence coloring ⋮ Revisiting semistrong edge‐coloring of graphs ⋮ Unnamed Item ⋮ Recent progress on strong edge-coloring of graphs ⋮ Strong edge-colorings of sparse graphs with \(3\Delta-1\) colors

Cites Work

• Unnamed Item
• Unnamed Item
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• Induced matchings in bipartite graphs
• On a packing and covering problem
• A dense infinite Sidon sequence
• A bound on the strong chromatic index of a graph
• Counting cycles and finite dimensional \(L^{p}\) norms
• Asymptotically good list-colorings
• A Short Proof That χ Can be Bounded ε Away from Δ + 1 toward ω
• A Stronger Bound for the Strong Chromatic Index
• Hitting all maximum cliques with a stable set using lopsided independent transversals
• Graph colouring and the probabilistic method

This page was built for publication: Colouring graphs with sparse neighbourhoods: bounds and applications