Consecutive colorings of graphs. (English) Zbl 0633.05027

In a simple graph \(G=(X,E)\) a positive integer \(c_ i\) is associated with every node i. We consider node colorings where node i receives a set S(i) of \(c_ i\) consecutive colors and \(S(i)\cap S(j)=\emptyset\) whenever nodes i and j are linked in G. Upper bounds on the minimum number of colors needed are derived. The case of perfect graphs is discussed.


05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
Full Text: DOI


[1] Golumbic MC (1980) Algorithmic graph theory and perfect graphs. Academic Press · Zbl 0541.05054
[2] Cangalovic M (1987) Exact colouring algorithm for vertex-composite graphs applied to timetable problems with multiple period lessons. Memorandum No 631. Department of Applied Mathematics, Twente University of Technology, Enschede
[3] Matula DW. Beck LL (1983) Smallest-last ordering and clustering and graph coloring algorithms. J ACM 30:417–427 · Zbl 0628.68054 · doi:10.1145/2402.322385
[4] Preissmann M, de Werra D (1985) A note on strong perfectness of graphs. Mathematical Programming 31:321–326 · Zbl 0587.05028 · doi:10.1007/BF02591953
[5] Szekeres G, Wilf H (1968) An inequality for the chromatic number of a graph. J Combinatorial Th 4:1–3 · Zbl 0171.44901 · doi:10.1016/S0021-9800(68)80081-X
[6] Welsh DJA, Powell MB (1967) An upper bound on the chromatic number of a graph and its application to timetabling problems. Computer J 10:85–87 · Zbl 0147.15206 · doi:10.1093/comjnl/10.1.85
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.