Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-07T15:19:00.807Z Has data issue: false hasContentIssue false
  • English
  • Français

Equitable Colourings of d-degenerate Graphs

Published online by Cambridge University Press:  28 January 2003

A. V. KOSTOCHKA  and
K. NAKPRASIT
A. V. KOSTOCHKA
Affiliation:
University of Illinois, Urbana, IL 61801, USA Institute of Mathematics, Novosibirsk, Russia 630090
K. NAKPRASIT
Affiliation:
Institute of Mathematics, Novosibirsk, Russia 630090
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A proper vertex coloring of a graph is called equitable if the sizes of colour classes differ by at most 1. In this paper, we find the minimum number l=l(d, Δ) such that every d-degenerate graph with maximum degree at most Δ admits an equitable t-colouring for every t[ges ]l when Δ[ges ]27d.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 12 , Issue 1 , January 2003 , pp. 53 - 60
Copyright
2003 Cambridge University Press