Distance-two coloring of sparse graphs

DOI10.1016/J.EJC.2013.09.002MaRDI QIDQ2441647zbMATH OpenOpenAlexFDO

Authors Zdeněk Dvořák, L. Esperet

Publication date 25 March 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

\(\varSigma\)-coloringclasses of bounded expansionnowhere-dense classes

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15)

Abstract: Consider a graph $G=(V,E)$ and, for each vertex $vinV$, a subset $Sigma(v)$ of neighbors of $v$. A $Sigma$-coloring is a coloring of the elements of $V$ so that vertices appearing together in some $Sigma(v)$ receive pairwise distinct colors. An obvious lower bound for the minimum number of colors in such a coloring is the maximum size of a set $Sigma(v)$, denoted by $ho(Sigma)$. In this paper we study graph classes $F$ for which there is a function $f$, such that for any graph $GinF$ and any $Sigma$, there is a $Sigma$-coloring using at most $f(ho(Sigma))$ colors. It is proved that if such a function exists for a class $F$, then $f$ can be taken to be a linear function. It is also shown that such classes are precisely the classes having bounded star chromatic number. We also investigate the list version and the clique version of this problem, and relate the existence of functions bounding those parameters to the recently introduced concepts of classes of bounded expansion and nowhere-dense classes.

Recommendations

• 2-distance coloring of sparse graphs
• 2-distance coloring of sparse graphs
• 2-distance list \((\varDelta +3)\)-coloring of sparse graphs
• The list 2-distance coloring of sparse graphs
• 2-distance coloring of sparse planar graphs

Cites work

• scientific article; zbMATH DE number 3900784 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 2209736 (Why is no real title available?)
• scientific article; zbMATH DE number 4187830 (Why is no real title available?)
• A unified approach to distance-two colouring of graphs on surfaces
• Bounding the vertex cover number of a hypergraph
• Coloring with no 2-colored \(P_4\)'s
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
• Graph minors. XVI: Excluding a non-planar graph
• Improper choosability and property B
• Largest planar graphs of diameter two and fixed maximum degree
• Linear time low tree-width partitions and algorithmic consequences
• On forbidden subdivision characterizations of graph classes
• On nowhere dense graphs
• Sparsity. Graphs, structures, and algorithms
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree

Cited in

(4)

• Star colouring of bounded degree graphs and regular graphs
• 2-distance coloring of sparse graphs
• Distance-2 Coloring in the CONGEST Model
• scientific article; zbMATH DE number 844150 (Why is no real title available?)

This page was built for publication: Distance-two coloring of sparse graphs

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