# zbMATH — the first resource for mathematics

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.

##### MSC:
 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
##### Keywords:
ordered colorings; trees; planar graphs; connectivity
Full Text:
##### References:
  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  Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1981), North-Holland New York · Zbl 1134.05001  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  Ding, G., Subgraphs and well-quasi-ordering, () · Zbl 0762.05093  Dzhidzhev, K.N., On the problem of partitioning planar graphs, SIAM, J. algorith. discrete meth., 3, 229-240, (1982)  Higman, G., Ordering by divisibility in abstract algebras, (), 326-336 · Zbl 0047.03402  Iyer, A.V.; Ratliff, H.D.; Vijayan, G., Analysis of parallelism in assembly operations, ()  Iyer, A.V.; Ratliff, H.D.; Vijayan, G., Optimal node ranking of trees, () · Zbl 0661.68063  Katchalski, M.; McCuaig, W.; Seager, S., Ordered colourings, () · Zbl 0842.05032  Leiserson, C.E., Area-efficient graph layouts (for VLSI), (), 270-281  Lipton, R.J.; Tarjan, R.E., A separator theorem for planar graphs, (), 1-10  Llewellyn, D.C.; Tovey, C.; Trick, M., Local optimization on graphs, Discrete appl. math., 23, 157-178, (1989) · Zbl 0675.90085  McCuaig, W.D., Ordered colourings of line graphs of trees, () · Zbl 0532.05041  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.