On coloring numbers of graph powers

DOI10.1016/J.DISC.2019.111712zbMATH Open1437.05074arXiv1907.10962OpenAlexW2962829512MaRDI QIDQ2174571FDOQ2174571

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

Publication date: 21 April 2020

Published in: Discrete Mathematics (Search for Journal in Brave)

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$.

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

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

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)

Cites Work

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

Cited In (8)

• Colouring graphs with bounded generalized colouring number
• Uniform orderings for generalized coloring numbers
• Title not available (Why is that?)
• Title not available (Why is that?)
• On \(b\)-coloring of powers of hypercubes
• On cocolourings and cochromatic numbers of graphs
• Cliques in squares of graphs with maximum average degree less than 4
• Coloring Powers of Chordal Graphs

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)