Total Coloring With $\Delta + \mbox\lowercasepoly(\log \Delta)$ Colors
Authors:
- Hugh HindHHHugh Hind
- Michael MolloyMMMichael Molloy
- Bruce ReedBRBruce Reed
- 1 January 1998
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 28 (3) , 816-821
Abstract
We provide a polynomial time algorithm which finds a total coloring of any graph with maximum degree $\D$, $\D$ sufficiently large, using at most $\D+8\log^8\D$ colors. This improves the best previous upper bound on the total chromatic number of $\D+18\D^{1/3}\log(3\D)$.
Keywords
This publication has 10 references indexed in Scilit:
- On a graph colouring problemDiscrete Mathematics, 1999
- A Bound on the Total Chromatic NumberCombinatorica, 1998
- Graphs whose choice number is equal to their chromatic numberJournal of Graph Theory, 1998
- Recent developments in total colouringDiscrete Mathematics, 1994
- Fractionally colouring total graphsCombinatorica, 1993
- A parallel algorithmic version of the local lemmaRandom Structures & Algorithms, 1991
- An algorithmic approach to the Lovász local lemma. IRandom Structures & Algorithms, 1991
- An upper bound for the total chromatic numberGraphs and Combinatorics, 1990
- An O(v|v| c |E|) algoithm for finding maximum matching in general graphs1980
- An O (N2.5) algorithm for maximum matching in general graphs1975