2-distance coloring of sparse graphs
For an undirected graph \(G,\) let \(\Delta (G)\) denote the maximum degree of \(G\) and \(\operatorname{mad}(G)\) denote the maximum of \(\sum_{v\in V(H)}d_H(v)/|V(H)|\) taken over all subgrahps \(H\) of \( G\). A 2-distance \(k\)-coloring assigns a color from the set of \(k\) colors to any vertex of \(G\) such that two vertices have different colors if they are adjacent or they have a common neighbor. If a set of \(k\) colors is assigned to every vertex and its color is taken from this set then 2-distance coloring is 2-distance \(k\)-list coloring and, moreover, if distinct neighbors of a vertex have distinct colors then we talk about injective 2-distance \(k\)-list coloring. Let \(\chi^2(G)\) denote the smallest \(k\) such that \(G\) admits 2-distance \(k\)-coloring and \(\chi_l^2(G)\) denote the smallest \(k\) such that \(G\) admits \(2\)-distance \(k\)-list coloring. It is proved that if \(G\) is a graph such that \(\Delta (G)\geq 4\) and \(\operatorname{mad}(G)<\frac 7 3\) then \(\chi^2(G)=\Delta (G)+1\) (these bounds are optimal), if \(G\) is a graph such that \(\Delta (G)\geq 5\) and \(\operatorname{mad}(G)<\frac {12}5\) or \(\Delta (G)\geq 6\) and \(\operatorname{mad}(G)<\frac 52\) or \(\Delta (G)\geq 8\) and \(\operatorname{mad}(G)<\frac {18}7\) then \(\chi^2_l(G)=\Delta (G)+1\) (and there exists an injective \(2\)-distance \((\Delta (G)+1)\)-list coloring). There exist functions \(f\) and \(h\) such that if \(G\) is a graph with \(\operatorname{mad}(G)<\frac {14}5-\epsilon\) and \(\Delta (G)\geq f(\epsilon )\) then \( \chi^2_l(G)=\Delta (G)+1\) and if \(G\) is a graph with \(\operatorname{mad}(G)<4-\epsilon\) then \(\chi^2_l(G)\leq\Delta (G)+h (\epsilon )\). Several consequences for planar graphs are derived. The presented proofs yield algorithms for the solution of these problems.
- 2-distance coloring of sparse graphs
- Distance-two coloring of sparse graphs
- 2-distance coloring of sparse planar graphs
- 2-distance coloring of sparse planar graphs
- The list 2-distance coloring of sparse graphs
- Near-proper vertex 2-colorings of sparse graphs
- 2-distance colorings of integer distance graphs
- Further results on 2-distance coloring of graphs
- 2-distance list \((\varDelta +3)\)-coloring of sparse graphs
- 2-distance 4-colorability of planar subcubic graphs with girth at least 22
- 2-distance coloring of sparse graphs
- 2-distance coloring of sparse planar graphs
- Choosability conjectures and multicircuits
- Coloring squares of planar graphs with girth six
- Counterexamples to the list square coloring conjecture
- Distance constrained labelings of planar graphs with no short cycles
- Every planar map is four colorable. I: Discharging
- Every planar map is four colorable. II: Reducibility
- scientific article; zbMATH DE number 5279355 (Why is no real title available?)
- Labeling Planar Graphs with Conditions on Girth and Distance Two
- On the maximum average degree and the oriented chromatic number of a graph
- On the total coloring of planar graphs.
- Facial incidence colorings of embedded multigraphs
- List r-hued chromatic number of graphs with bounded maximum average degrees
- 2-distance colorings of integer distance graphs
- List r-dynamic coloring of graphs with small maximum average degree
- 2-distance list \((\varDelta +3)\)-coloring of sparse graphs
- A characterization of graphs with regular distance-2 graphs
- List 2-distance coloring of planar graphs with girth five
- 2-distance list ( +2)-coloring of planar graphs with girth at least 10
- Graph \(r\)-hued colorings -- a survey
- \(r\)-hued \((r+1)\)-coloring of planar graphs with girth at least 8 for \(r\geq 9\)
- Incidence coloring -- cold cases
- The k-distance chromatic number of trees and cycles
- Incidence coloring of graphs with high maximum average degree
- Distance-two coloring of sparse graphs
- Hypergraph incidence coloring
- Coloring the square of a sparse graph G with almost (G) colors
- On 1-improper 2-coloring of sparse graphs
- List 2-distance coloring of graphs with maximum degree 5
- scientific article; zbMATH DE number 844150 (Why is no real title available?)
- An introduction to the discharging method via graph coloring
- Distance-2 Coloring in the CONGEST Model
- Finding cut-vertices in the square roots of a graph
- Incidence coloring of outer-1-planar graphs
- 2-distance \((\Delta + 1)\)-coloring of sparse graphs using the potential method
- Proper additive choice number of planar graphs
- 2-distance 4-coloring of planar subcubic graphs with girth at least 21
- List coloring the square of sparse graphs with large degree
- The list 2-distance coloring of sparse graphs
- Coloring the square of graphs whose maximum average degree is less than 4
This page was built for publication: 2-distance coloring of sparse graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6486785)
