Injective colorings of graphs with low average degree

DOI10.1007/S00453-010-9425-XMaRDI QIDQ548659zbMATH OpenOpenAlexWikidataFDO

Authors Daniel W. Cranston, Seog-Jin Kim, Gexin Yu

Publication date 30 June 2011

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

list coloringdischarging methodmaximum average degreeinjective coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: Let $mad(G)$ denote the maximum average degree (over all subgraphs) of $G$ and let $ch{i}_i(G)$ denote the injective chromatic number of $G$. We prove that if $Deltageq4$ and $mad(G)<frac145$, then $ch{i}_i(G)leqDelta+2$. When $Delta=3$, we show that $mad(G)<frac3613$ implies $ch{i}_i(G)le5$. In contrast, we give a graph $G$ with $Delta=3$, $mad(G)=frac3613$, and $ch{i}_i(G)=6$.

Recommendations

• Injective colorings of sparse graphs
• Injective edge coloring of graphs with maximum degree 5
• Injectively delta choosable graphs
• Injective edge coloring of sparse graphs
• Two smaller upper bounds of List injective chromatic number

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A bound on the chromatic number of the square of a planar graph
• Coloring the square of a planar graph
• Grid Colorings in Steganography
• How the proof of the strong perfect graph conjecture was found
• Injective colorings of planar graphs with few colors
• Injective colorings of sparse graphs
• List edge and list total colourings of multigraphs
• List-coloring the square of a subcubic graph
• On the injective chromatic number of graphs
• On the total coloring of planar graphs.
• Some bounds on the injective chromatic number of graphs
• The four-colour theorem
• The strong perfect graph theorem
• The strong perfect graph theorem

Cited in

(36)

• Injective coloring of some subclasses of bipartite graphs and chordal graphs
• List injective coloring of planar graphs with girth g 6
• Injective colorings of sparse graphs
• Some bounds on the injective chromatic number of graphs
• Note on the perfect EIC-graphs
• Injective choosability of subcubic planar graphs with girth 6
• Maximum average degree and relaxed coloring
• Injective edge coloring of graphs with maximum degree 5
• Injective coloring of planar graphs with girth 7
• 2-distance, injective, and exact square list-coloring of planar graphs with maximum degree 4
• On coupon colorings of graphs
• Injective coloring of planar graphs with girth 5
• On injective chromatic polynomials of graphs
• Injective coloring of plane graphs with girth 5
• List injective coloring of planar graphs with girth 5, 6, 8
• Nordhaus-Gaddum-type relations of three graph coloring parameters
• Injective edge coloring of sparse graphs with maximum degree 5
• Injective coloring of Halin graphs
• Sufficient sparseness conditions for \(G^2\) to be \((\Delta + 1)\)-choosable, when \(\Delta \geq 5\)
• Injective coloring of planar graphs
• Two smaller upper bounds of List injective chromatic number
• scientific article; zbMATH DE number 7318748 (Why is no real title available?)
• 2-distance coloring of planar graphs with girth 5
• List injective coloring of planar graphs with girth \(g\geq 5\)
• Injective edge-coloring of claw-free subcubic graphs
• Connectivity of minimum non-5-injectively colorable planar cubic graphs
• Injectively delta choosable graphs
• Injective coloring of subclasses of chordal graphs
• List injective coloring of planar graphs
• List injective coloring of planar graphs with girth at least five
• An introduction to the discharging method via graph coloring
• Coupon coloring of some special graphs
• List injective coloring of a class of planar graphs without short cycles
• Injective edge coloring of sparse graphs
• On domatic number of graphs
• Injective choosability of planar graphs of girth five and six

This page was built for publication: Injective colorings of graphs with low average degree

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