Ordered colourings. (English) Zbl 0842.05032

An ordered \(k\)-coloring of a graph \(G\) is a coloring function \(c: V(G)\to \{1, 2,\dots, k\}\) such that, for every pair of distinct vertices \(x\) and \(y\) and for every \(x\)-\(y\) path \(P\), if \(c(x)= c(y)\), then there exists an internal vertex \(z\) of \(P\) such that \(c(x)< c(z)\). This paper proves some results about ordered colorings of trees and planar graphs. For example, if every planar graph has an ordered coloring using at least \(g(v)\) vertices, then \(g(v)\leq 3(\sqrt 6+ 2)\sqrt v\). The paper also examines the relationship between connectivity and ordered colorings.


05C15 Coloring of graphs and hypergraphs
05C05 Trees
05C10 Planar graphs; geometric and topological aspects of graph theory
05C35 Extremal problems in graph theory
05C40 Connectivity
Full Text: DOI


[1] Grötschel, M.; Pulleyblank, W.R., Clique tree inequalities and the symmetric travelling salesman problem, Math. oper. res., 11, 537-569, (1986) · Zbl 0626.90060
[2] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1981), North-Holland New York · Zbl 1134.05001
[3] Boyd, S.C.; Pulleyblank, W.R., Optimizing over the subtour polytope of the travelling salesman problem, Math. program. ser. A, 49, 2, 163-187, (1990) · Zbl 0726.90086
[4] Ding, G., Subgraphs and well-quasi-ordering, () · Zbl 0762.05093
[5] Dzhidzhev, K.N., On the problem of partitioning planar graphs, SIAM, J. algorith. discrete meth., 3, 229-240, (1982)
[6] Higman, G., Ordering by divisibility in abstract algebras, (), 326-336 · Zbl 0047.03402
[7] Iyer, A.V.; Ratliff, H.D.; Vijayan, G., Analysis of parallelism in assembly operations, ()
[8] Iyer, A.V.; Ratliff, H.D.; Vijayan, G., Optimal node ranking of trees, () · Zbl 0661.68063
[9] Katchalski, M.; McCuaig, W.; Seager, S., Ordered colourings, () · Zbl 0842.05032
[10] Leiserson, C.E., Area-efficient graph layouts (for VLSI), (), 270-281
[11] Lipton, R.J.; Tarjan, R.E., A separator theorem for planar graphs, (), 1-10
[12] Llewellyn, D.C.; Tovey, C.; Trick, M., Local optimization on graphs, Discrete appl. math., 23, 157-178, (1989) · Zbl 0675.90085
[13] McCuaig, W.D., Ordered colourings of line graphs of trees, () · Zbl 0532.05041
[14] Robertson, N.; Seymour, P.D., Graph minors — a survey, (), 153-171, Glasgow, 1985 · Zbl 0568.05025
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.