Injective colorings of graphs with low average degree

DOI10.1007/S00453-010-9425-XzbMath1218.05046arXiv1006.3776OpenAlexW1988435782WikidataQ114229332 ScholiaQ114229332MaRDI QIDQ548659

Seog-Jin Kim, Daniel W. Cranston, 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)

Related Items (29)

INJECTIVE COLORING OF PLANAR GRAPHS WITH GIRTH 7 ⋮ On injective chromatic polynomials of graphs ⋮ Injective coloring of planar graphs with girth 5 ⋮ List injective coloring of a class of planar graphs without short cycles ⋮ List injective coloring of planar graphs ⋮ Unnamed Item ⋮ Injective coloring of some subclasses of bipartite graphs and chordal graphs ⋮ Connectivity of minimum non-5-injectively colorable planar cubic graphs ⋮ 2-distance coloring of planar graphs with girth 5 ⋮ Injective coloring of plane graphs with girth 5 ⋮ 2-distance, injective, and exact square list-coloring of planar graphs with maximum degree 4 ⋮ Injective choosability of planar graphs of girth five and six ⋮ List injective coloring of planar graphs with girth 5, 6, 8 ⋮ Unnamed Item ⋮ Note on the perfect EIC-graphs ⋮ An introduction to the discharging method via graph coloring ⋮ Coupon coloring of some special graphs ⋮ LIST INJECTIVE COLORING OF PLANAR GRAPHS WITH GIRTH g ≥ 5 ⋮ Two smaller upper bounds of List injective chromatic number ⋮ Injective coloring of planar graphs ⋮ Injective choosability of subcubic planar graphs with girth 6 ⋮ On domatic number of graphs ⋮ Injective coloring of Halin graphs ⋮ List injective coloring of planar graphs with girth \(g \geq 6\) ⋮ Injective edge-coloring of claw-free subcubic graphs ⋮ Sufficient sparseness conditions for \(G^2\) to be \((\Delta + 1)\)-choosable, when \(\Delta \geq 5\) ⋮ Nordhaus-Gaddum-type relations of three graph coloring parameters ⋮ Injective coloring of subclasses of chordal graphs ⋮ On coupon colorings of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Injective colorings of sparse graphs
• The strong perfect graph theorem
• Some bounds on the injective chromatic number of graphs
• Injective colorings of planar graphs with few colors
• List edge and list total colourings of multigraphs
• The four-colour theorem
• On the injective chromatic number of graphs
• A bound on the chromatic number of the square of a planar graph
• List-coloring the square of a subcubic graph
• Grid Colorings in Steganography
• On the total coloring of planar graphs.
• Coloring the square of a planar graph

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