[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Coloring Graphs with Sparse Neighborhoods

Published: 01 September 1999 Publication History

Abstract

It is shown that the chromatic number of any graph with maximum degree d in which the number of edges in the induced subgraph on the set of all neighbors of any vertex does not exceed d2/f is at most O(d/logf). This is tight (up to a constant factor) for all admissible values of d and f.

References

[1]
M. Ajtai, J. Komlós, E. Szemerédi, A dense infinite Sidon sequence, European J. Combin., 2 (1981) 1-11.
[2]
N. Alon, The strong chromatic number of a graph, Random Structures Algorithms, 3 (1992) 1-7.
[3]
N. Alon, M. Krivelevich, and, B. Sudakov, List coloring of random and pseudo-random graphs, Combinatorica, to appear.
[4]
N. Alon, J. Spencer, Wiley, New York, 1992.
[5]
R.L. Brooks, On coloring the nodes of a network, Math. Proc. Cambridge Philos. Soc., 37 (1941) 194-197.
[6]
B. Bollobás, Chromatic number, girth and maximal degree, Discrete Math., 24 (1978) 311-314.
[7]
A. R. Johansson, Asymptotic choice number for triangle free graphs, to appear.
[8]
A. R. Johansson, The choice number of sparse graphs, manuscript, 1998.
[9]
T. Jensen, B. Toft, Wiley, New York, 1995.
[10]
A.V. Kostochka, N.P. Mazurova, An inequality in the theory of graph coloring, Metody Diskret. Anal., 30 (1977) 23-29.
[11]
L. Lovász, North-Holland, Amsterdam, 1993.
[12]
C.J.H. McDiarmid, On the method of bounded differences, in: London Math. Soc. Lecture Notes Series, 141, Cambridge Univ. Press, Cambridge, 1989, pp. 148-188.
[13]
M. Molloy, B. Reed, A bound on the strong chromatic index of a graph, J. Combin. Theory Ser. B, 69 (1997) 103-109.
[14]
V.G. Vizing, On a estimate on the chromatic class of a p-graph, Diskret. Anal., 3 (1964) 25-30.

Cited By

View all
  • (2023)Uniformly Random Colourings of Sparse GraphsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585242(1357-1370)Online publication date: 2-Jun-2023
  • (2023)Improved Gilbert-Varshamov Bounds for Hopping Cyclic Codes and Optical Orthogonal CodesIEEE Transactions on Information Theory10.1109/TIT.2023.329696369:11(7099-7109)Online publication date: 1-Nov-2023
  • (2021)An improved procedure for colouring graphs of bounded local densityProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458074(135-148)Online publication date: 10-Jan-2021
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Combinatorial Theory Series B
Journal of Combinatorial Theory Series B  Volume 77, Issue 1
Sept. 1999
219 pages
ISSN:0095-8956
Issue’s Table of Contents

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 September 1999

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 05 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Uniformly Random Colourings of Sparse GraphsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585242(1357-1370)Online publication date: 2-Jun-2023
  • (2023)Improved Gilbert-Varshamov Bounds for Hopping Cyclic Codes and Optical Orthogonal CodesIEEE Transactions on Information Theory10.1109/TIT.2023.329696369:11(7099-7109)Online publication date: 1-Nov-2023
  • (2021)An improved procedure for colouring graphs of bounded local densityProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458074(135-148)Online publication date: 10-Jan-2021
  • (2020)Dense Induced Bipartite Subgraphs in Triangle-Free GraphsCombinatorica10.1007/s00493-019-4086-040:2(283-305)Online publication date: 16-Jan-2020
  • (2017)Triangle-free graphs of tree-width t are (t+3)2-colorableEuropean Journal of Combinatorics10.1016/j.ejc.2017.06.01666:C(95-100)Online publication date: 1-Dec-2017
  • (2017)Distributed algorithms for the Lovász local lemma and graph coloringDistributed Computing10.1007/s00446-016-0287-630:4(261-280)Online publication date: 1-Aug-2017
  • (2015)(2Δ − 1)-edge-coloring is much easier than maximal matching in the distributed settingProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722155(355-370)Online publication date: 4-Jan-2015
  • (2015)On the Lovász Theta function for Independent Sets in Sparse GraphsProceedings of the forty-seventh annual ACM symposium on Theory of Computing10.1145/2746539.2746607(193-200)Online publication date: 14-Jun-2015
  • (2015)Distributed coloring algorithms for triangle-free graphsInformation and Computation10.1016/j.ic.2014.12.018243:C(263-280)Online publication date: 1-Aug-2015
  • (2015)List coloring triangle-free hypergraphsRandom Structures & Algorithms10.1002/rsa.2055247:3(487-519)Online publication date: 1-Oct-2015
  • Show More Cited By

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media