Injective colorings of graphs with low average degree

DOI10.1007/S00453-010-9425-XzbMATH Open1218.05046arXiv1006.3776OpenAlexW1988435782WikidataQ114229332 ScholiaQ114229332MaRDI QIDQ548659FDOQ548659

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

Publication date: 30 June 2011

Published in: Algorithmica (Search for Journal in Brave)

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

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

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

zbMATH Keywords

list coloringdischarging methodmaximum average degreeinjective coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

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

Cited In (31)

• List injective coloring of planar graphs with girth \(g \geq 6\)
• Note on the perfect EIC-graphs
• Injective choosability of subcubic planar graphs with girth 6
• Injective edge coloring of graphs with maximum degree 5
• 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
• LIST INJECTIVE COLORING OF PLANAR GRAPHS WITH GIRTH g ≥ 5
• Injective coloring of plane graphs with girth 5
• List injective coloring of planar graphs with girth 5, 6, 8
• Title not available (Why is that?)
• Injective edge coloring of sparse graphs with maximum degree 5
• Nordhaus-Gaddum-type relations of three graph coloring parameters
• Injective coloring of Halin graphs
• Injective coloring of planar graphs
• Sufficient sparseness conditions for \(G^2\) to be \((\Delta + 1)\)-choosable, when \(\Delta \geq 5\)
• INJECTIVE COLORING OF PLANAR GRAPHS WITH GIRTH 7
• Two smaller upper bounds of List injective chromatic number
• Title not available (Why is that?)
• 2-distance coloring of planar graphs with girth 5
• Injective edge-coloring of claw-free subcubic graphs
• Connectivity of minimum non-5-injectively colorable planar cubic graphs
• Injective coloring of subclasses of chordal graphs
• List injective coloring of planar graphs
• 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
• On domatic number of graphs
• Injective choosability of planar graphs of girth five and six
• Injective coloring of some subclasses of bipartite graphs and chordal graphs

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)