Coloring graphs with sparse neighborhoods

DOI10.1006/jctb.1999.1910zbMath1026.05043OpenAlexW2048800330MaRDI QIDQ1569053

Michael Krivelevich, Noga Alon, Benjamin Sudakov

Publication date: 25 June 2000

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

Full work available at URL: https://doi.org/10.1006/jctb.1999.1910

zbMATH Keywords

chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items

Colouring graphs with forbidden bipartite subgraphs, The list chromatic number of graphs with small clique number, List coloring triangle-free hypergraphs, A stronger bound for the strong chromatic index (extended abstract), Triangle-free graphs of tree-width \(t\) are \(\lceil (t+3)/2 \rceil\)-colorable, On the Lovász Theta Function for Independent Sets in Sparse Graphs, Occupancy fraction, fractional colouring, and triangle fraction, Graph and hypergraph colouring via nibble methods: a survey, Distance colouring without one cycle length, A proof of the Erdős-Faber-Lovász conjecture, Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering, A Stronger Bound for the Strong Chromatic Index, On triangle-free list assignments, Packing list‐colorings, Conflict-free coloring for rectangle ranges using \(O(n ^{.382})\) colors, Unnamed Item, Randomly colouring graphs (a combinatorial view), Ramsey numbers of some bipartite graphs versus complete graphs, Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers, Lower bounds for independence numbers of some locally sparse graphs, Random regular graphs of high degree, On independent sets in hypergraphs, The Distance-t Chromatic Index of Graphs, Dense induced bipartite subgraphs in triangle-free graphs, The strong chromatic index ofC4-free graphs, Coloring H-free hypergraphs, On the Chromatic Number of Random Graphs with a Fixed Degree Sequence, The chromatic number of random Cayley graphs, On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs, Structure and colour in triangle-free graphs, Multicolor Ramsey numbers via pseudorandom graphs, Distance Colouring Without One Cycle Length, Coloring Sparse Hypergraphs, Short proofs of some extremal results III, Distributed algorithms for the Lovász local lemma and graph coloring, Coloring Powers and Girth, Independent Sets in Polarity Graphs, The Final Size of theC₄-Free Process, Edge‐coloring linear hypergraphs with medium‐sized edges, Independent dominating sets in graphs of girth five, Mixing properties of colourings of the ℤ^d lattice, The C_ℓ‐free process, Some Results on Chromatic Number as a Function of Triangle Count, Two Chromatic Conjectures: One for Vertices and One for Edges, On the chromatic number of the Erdős-Rényi orthogonal polarity graph, Distributed coloring algorithms for triangle-free graphs

Cites Work

• A dense infinite Sidon sequence
• Chromatic number, girth and maximal degree
• A bound on the strong chromatic index of a graph
• List coloring of random and pseudo-random graphs
• The strong chromatic number of a graph
• The Solution of a Timetabling Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item