Coloring powers and girth

DOI10.1137/15M1035422MaRDI QIDQ2827489zbMATH OpenOpenAlexFDO

Authors Ross J. Kang, François Pirot

Publication date 20 October 2016

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

girthgraph coloringgraph powers

Mathematics Subject Classification ID

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)

Abstract: Alon and Mohar (2002) posed the following problem: among all graphs $G$ of maximum degree at most $d$ and girth at least $g$, what is the largest possible value of $chi(G^t)$, the chromatic number of the $t$th power of $G$? For $tge3$, we provide several upper and lower bounds concerning this problem, all of which are sharp up to a constant factor as $doinfty$. The upper bounds rely in part on the probabilistic method, while the lower bounds are various direct constructions whose building blocks are incidence structures.

Recommendations

• The Chromatic Number of Graph Powers
• The distance-t chromatic index of graphs
• The distance coloring of graphs
• On coloring numbers of graph powers
• Publication:4952682

Cites work

• Coloring graphs with sparse neighborhoods
• Graph colouring and the probabilistic method
• scientific article; zbMATH DE number 3877205 (Why is no real title available?)
• scientific article; zbMATH DE number 3284071 (Why is no real title available?)
• Moore graphs and beyond: a survey of the degree/diameter problem
• On maximal paths and circuits of graphs
• ON THE DIFFERENCE BETWEEN CONSECUTIVE PRIMES
• The Chromatic Number of Graph Powers
• The distance-t chromatic index of graphs
• The nonexistence of certain generalized polygons

Cited in

(9)

• On colorings of graph powers
• On small graphs with highly imperfect powers
• Distance colouring without one cycle length
• Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
• The Chromatic Number of Graph Powers
• Distance colouring without one cycle length
• t-strong cliques and the degree-diameter problem
• The distance-t chromatic index of graphs
• Algebraic bounds for the independence and chromatic number of graph powers

This page was built for publication: Coloring powers and girth

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