Chromatic number, girth and maximal degree

DOI10.1016/0012-365X(78)90102-4zbMath0395.05034OpenAlexW2036489778MaRDI QIDQ1252865

Béla Bollobás

Publication date: 1978

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(78)90102-4

zbMATH Keywords

GirthChromatic NumberMaximal Degree

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15)

Related Items

Dominator and total dominator coloring of circulant graph C_n(1, 2) ⋮ Digraphs and Variable Degeneracy ⋮ Symmetry breaking depending on the chromatic number or the neighborhood growth ⋮ Directed acyclic graphs with the unique dipath property ⋮ On Brooks' Theorem for Sparse Graphs ⋮ Degree sequences of random graphs ⋮ Two results on the digraph chromatic number ⋮ Extremal problems in hypergraph colourings ⋮ On triangle-free list assignments ⋮ Unnamed Item ⋮ Randomly colouring graphs (a combinatorial view) ⋮ An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model ⋮ The edge density of critical digraphs ⋮ Component Games on Regular Graphs ⋮ Large induced forests in sparse graphs ⋮ Improved distributed algorithms for coloring interval graphs with application to multicoloring trees ⋮ Coloring graphs with sparse neighborhoods ⋮ Distributed coloring algorithms for triangle-free graphs

Cites Work

• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• A bound on the chromatic number of a graph
• Graph Theory and Probability
• Unnamed Item
• Unnamed Item
• Unnamed Item