On coloring numbers of graph powers

DOI10.1016/J.DISC.2019.111712MaRDI QIDQ2174571zbMATHOpenAlexFDO

Authors Daqing Yang, Junjun Yi, H. A. Kierstead

Publication date 21 April 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph powersquare of graphsmaximum average degreecoloring numberharmonious strategyweak coloring number

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15)

Abstract: The weak $r$-coloring numbers $wco{l}_r(G)$ of a graph $G$ were introduced by the first two authors as a generalization of the usual coloring number $col(G)$, and have since found interesting theoretical and algorithmic applications. This has motivated researchers to establish strong bounds on these parameters for various classes of graphs. Let $G^p$ denote the $p$-th power of $G$. We show that, all integers $p>0$ and $Deltage3$ and graphs $G$ with $Delta(G)leqDelta$ satisfy $col(G^p)inO(pcdotwco{l}_{lceilp/2ceil}(G)(Delta-1{)}^{lfloorp/2floor})$; for fixed tree width or fixed genus the ratio between this upper bound and worst case lower bounds is polynomial in $p$. For the square of graphs $G$, we also show that, if the maximum average degree $2k-2<mad(G)leq2k$, then $col(G^2)leq(2k-1)Delta(G)+2k+1$.

Recommendations

• Publication:4952682
• Improved bounds for weak coloring numbers
• Note on the game colouring number of powers of graphs
• The Chromatic Number of Graph Powers
• Coloring Powers of Planar Graphs

Cites work

• A simple competitive graph coloring algorithm
• Chromatic numbers of exact distance graphs
• Coloring Powers of Chordal Graphs
• Coloring Powers of Planar Graphs
• Coloring and covering nowhere dense graphs
• Coloring games on squares of graphs
• Coloring squares of graphs with mad constraints
• Coloring squares of planar graphs with girth six
• Coloring the square of graphs whose maximum average degree is less than 4
• Colouring graphs with bounded generalized colouring number
• Competitive colorings of oriented graphs
• Constant-factor approximation of the domination number in sparse graphs
• Decomposition of Finite Graphs Into Forests
• Generalization of transitive fraternal augmentations for directed graphs and its applications
• Grad and classes with bounded expansion. I: Decompositions
• Graphs with linearly bounded Ramsey numbers
• Improper colourings inspired by Hadwiger's conjecture
• List coloring the square of sparse graphs with large degree
• On the degrees of the vertices of a directed graph
• On the generalised colouring numbers of graphs that exclude a fixed minor
• Orderings on graphs and game coloring number
• Radius two trees specify χ‐bounded classes
• Sparsity. Graphs, structures, and algorithms
• Uniform orderings for generalized coloring numbers
• Very asymmetric marking games

Cited in

(12)

• A Brooks-like result for graph powers
• scientific article; zbMATH DE number 6518587 (Why is no real title available?)
• Note on the game colouring number of powers of graphs
• On \(b\)-coloring of powers of hypercubes
• Coloring Powers of Chordal Graphs
• On cocolourings and cochromatic numbers of graphs
• Improved bounds for weak coloring numbers
• Cliques in squares of graphs with maximum average degree less than 4
• Colouring graphs with bounded generalized colouring number
• scientific article; zbMATH DE number 1445362 (Why is no real title available?)
• Coloring powers and girth
• Uniform orderings for generalized coloring numbers

This page was built for publication: On coloring numbers of graph powers

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