Tree-like distance colouring for planar graphs of sufficient girth (Q668079)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Tree-like distance colouring for planar graphs of sufficient girth |
scientific article |
Statements
Tree-like distance colouring for planar graphs of sufficient girth (English)
0 references
5 March 2019
0 references
Summary: Given a multigraph \(G\) and a positive integer \(t\), the distance-\(t\) chromatic index of \(G\) is the least number of colours needed for a colouring of the edges so that every pair of distinct edges connected by a path of fewer than \(t\) edges must receive different colours. Let \(\pi'_t(d)\) and \(\tau'_t(d)\) be the largest values of this parameter over the class of planar multigraphs and of (simple) trees, respectively, of maximum degree \(d\). We have that \(\pi'_t(d)\) is at most and at least a non-trivial constant multiple larger than \(\tau'_t(d)\). (We conjecture \(\limsup_{d\rightarrow\infty}\pi'_2(d)/\tau'_2(d) =9/4\) in particular.) We prove for odd \(t\) the existence of a quantity \(g\) depending only on \(t\) such that the distance-\(t\) chromatic index of any planar multigraph of maximum degree \(d\) and girth at least \(g\) is at most \(\tau'_t(d)\) if \(d\) is sufficiently large. Such a quantity does not exist for even \(t\). We also show a related, similar phenomenon for distance vertex-colouring.
0 references
0 references