The distance-t chromatic index of graphs

DOI10.1017/S0963548313000473MaRDI QIDQ5414148zbMATH OpenFDO

Authors Tomáš Kaiser, Ross J. Kang

Publication date 2 May 2014

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.4171

zbMATH Keywords

Molloy and Reed's bound on the strong chromatic index

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: We consider two graph colouring problems in which edges at distance at most $t$ are given distinct colours, for some fixed positive integer $t$. We obtain two upper bounds for the distance-$t$ chromatic index, the least number of colours necessary for such a colouring. One is a bound of $(2-eps)Delt{a}^t$ for graphs of maximum degree at most $Delta$, where $eps$ is some absolute positive constant independent of $t$. The other is a bound of $O(Delt{a}^t/logDelta)$ (as $Deltaoinfty$) for graphs of maximum degree at most $Delta$ and girth at least $2t+1$. The first bound is an analogue of Molloy and Reed's bound on the strong chromatic index. The second bound is tight up to a constant multiplicative factor, as certified by a class of graphs of girth at least $g$, for every fixed $gge3$, of arbitrarily large maximum degree $Delta$, with distance-$t$ chromatic index at least $Omega(Delt{a}^t/logDelta)$.

Recommendations

• Tree-like distance colouring for planar graphs of sufficient girth
• Some maximum multigraphs and adge/vertex distance colourings
• A bound on the strong chromatic index of a graph
• t-strong cliques and the degree-diameter problem
• Coloring powers and girth

Cites work

• A bound on the strong chromatic index of a graph
• Coloring graphs with sparse neighborhoods
• Distance edge-colourings and matchings
• Graph Theory and Probability
• Induced matchings in bipartite graphs
• The nonexistence of certain generalized polygons
• The strong chromatic index ofC4-free graphs

Cited in

(12)

• Distance colouring without one cycle length
• Colouring graphs with sparse neighbourhoods: bounds and applications
• Coloring powers and girth
• A stronger bound for the strong chromatic index (extended abstract)
• A stronger bound for the strong chromatic index
• Distance colouring without one cycle length
• t-strong cliques and the degree-diameter problem
• Maximizing line subgraphs of diameter at most \(t\)
• \(t\)-strong cliques and the degree-diameter problem
• Tree-like distance colouring for planar graphs of sufficient girth
• Large induced distance matchings in certain sparse random graphs
• Eigenvalue bounds for distance-edge colourings

This page was built for publication: The distance-\(t\) chromatic index of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5414148)