Injective colorings of sparse graphs

DOI10.1016/J.DISC.2010.07.003zbMATH Open1209.05075arXiv1007.0786OpenAlexW2057330543WikidataQ114190774 ScholiaQ114190774MaRDI QIDQ710598FDOQ710598

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

Publication date: 19 October 2010

Published in: Discrete Mathematics (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 $mad(G)leq5/2$, then $ch{i}_i(G)leqDelta(G)+1$; and if $mad(G)<42/19$, then $ch{i}_i(G)=Delta(G)$. Suppose that $G$ is a planar graph with girth $g(G)$ and $Delta(G)geq4$. We prove that if $g(G)geq9$, then $ch{i}_i(G)leqDelta(G)+1$; similarly, if $g(G)geq13$, then $ch{i}_i(G)=Delta(G)$.

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

Recommendations

• Injective colorings of graphs with low average degree
• Injective coloring of planar graphs
• Injective choosability of planar graphs of girth five and six
• Injective edge coloring of sparse graphs with maximum degree 5
• Injective coloring of planar graphs with girth 5

zbMATH Keywords

planar graphmaximum average degreeinjective coloring

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• List edge and list total colourings of multigraphs
• Title not available (Why is that?)
• On the total coloring of planar graphs.
• Title not available (Why is that?)
• Multicriterial graph problems with MAXMIN criterion
• 2-distance \((\varDelta +2)\)-coloring of planar graphs with girth six and \(\varDelta \geq 18\)
• Coloring squares of planar graphs with girth six
• The Chromatic Number of Graph Powers
• Injective colorings of planar graphs with few colors
• On the injective chromatic number of graphs
• Injective coloring of planar graphs
• Some bounds on the injective chromatic number of graphs
• Title not available (Why is that?)

Cited In (35)

• Remarks on proper conflict-free colorings of graphs
• List injective coloring of planar graphs with girth \(g \geq 6\)
• Injective colorings of graphs with low average degree
• Graph equation for line graphs and \(m\)-step graphs
• A note on odd colorings of 1-planar graphs
• List injective colorings of planar graphs
• Injective choosability of subcubic planar graphs with girth 6
• 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
• 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 some graph operations
• Injective colorings with arithmetic constraints
• Two smaller upper bounds of List injective chromatic number
• Title not available (Why is that?)
• List injective coloring of planar graphs with girth \(g\geq 5\)
• 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
• On domatic number of graphs
• Injective choosability of planar graphs of girth five and six
• Injective \(\Delta +2\) coloring of planar graph without short cycles
• Injective coloring of graphs revisited
• Injective \((\Delta + 1)\)-coloring of planar graphs with girth 6
• Injective coloring of some subclasses of bipartite graphs and chordal graphs

This page was built for publication: Injective colorings of sparse graphs

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