Ordered colourings
type: Item
instance of: scholarly article
title: Ordered colourings
zbMATH Open document ID: 0842.05032
DOI: 10.1016/0012-365X(93)E0216-Q
author: Meir Katchalski
author: William McCuaig
author: Suzanne Seager
published in: Discrete Mathematics
publication date: 1996-07-17T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 790756
zbMATH Keywords: ordered colorings
zbMATH Keywords: trees
zbMATH Keywords: planar graphs
zbMATH Keywords: connectivity
reviewed by: Alan C. Tucker
MaRDI profile type: Publication
cites work: Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
cites work: Q5422499
cites work: Optimizing over the subtour polytope of the travelling salesman problem
cites work: Subgraphs and well‐quasi‐ordering
cites work: On the Problem of Partitioning Planar Graphs
cites work: Ordering by Divisibility in Abstract Algebras
cites work: Optimal node ranking of trees
cites work: Q3206972
cites work: Local optimization on graphs
cites work: Cyclability of r-regular r-connected graphs
cites work: Q3684139
full work available at URL: 0012-365x(93)e0216-q
OpenAlex ID: W2913683243
description: scientific article; zbMATH DE number 790756