Some bounds on the injective chromatic number of graphs

DOI10.1016/J.DISC.2009.04.020MaRDI QIDQ960972zbMATH OpenOpenAlexWikidataFDO

Authors Alain Doyon, Geňa Hahn, André Raspaud

Publication date 29 March 2010

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2009.04.020

zbMATH Keywords

injective chromatic numbervertex colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

The authors consider the \textit{injective chromatic number} of a graph \(G\), which is defined as the minimal integer \(k\) such that there exists a colouring of the vertices of \(G\) with \(k\) colours, where no two vertices with a common neighbour have the same colour. Upper bounds for this injective chromatic number are derived in terms of the maximum degree of \(G\) and the maximum average degree of \(G\).

Recommendations

• Two smaller upper bounds of List injective chromatic number
• Some results on the injective chromatic number of graphs
• On the injective chromatic number of graphs
• Injective colorings of graphs with low average degree
• Sharp upper bound of injective coloring of planar graphs with girth at least 5

Cites work

• Graph theory
• scientific article; zbMATH DE number 1131873 (Why is no real title available?)
• Minimum partition of a matroid into independent subsets
• On the injective chromatic number of graphs

Cited in

(39)

• Injective colorings of planar graphs with few colors
• Injective coloring of some graph operations
• 2-distance coloring of planar graphs with girth 5
• Note on the perfect EIC-graphs
• On the injective chromatic number of graphs
• Graph equation for line graphs and \(m\)-step graphs
• Some results on the injective chromatic number of graphs
• Injective choosability of subcubic planar graphs with girth 6
• Injective coloring of Halin graphs
• Injective coloring of planar graphs with girth 5
• List injective coloring of planar graphs
• Connectivity of minimum non-5-injectively colorable planar cubic graphs
• Critical injective chromatic graphs
• Two smaller upper bounds of List injective chromatic number
• List injective coloring of planar graphs with girth 5, 6, 8
• Injective coloring of graphs revisited
• Injective coloring of planar graphs with girth 7
• On injective chromatic polynomials of graphs
• Injective coloring of planar graphs with girth 6
• Injective coloring of plane graphs with girth 5
• Locally injective k-colourings of planar graphs
• Injective choosability of planar graphs of girth five and six
• List injective coloring of a class of planar graphs without short cycles
• scientific article; zbMATH DE number 7318748 (Why is no real title available?)
• scientific article; zbMATH DE number 7452301 (Why is no real title available?)
• List injective coloring of planar graphs with disjoint 5^--cycles
• Coupon coloring of some special graphs
• List injective coloring of planar graphs with girth \(g\geq 5\)
• Injective colorings of graphs with low average degree
• Injective coloring of planar graphs
• Injective coloring of planar graphs
• 2-distance, injective, and exact square list-coloring of planar graphs with maximum degree 4
• Injective \(\Delta +2\) coloring of planar graph without short cycles
• List injective coloring of planar graphs with girth at least five
• On domatic number of graphs
• Injective colorings of wheel related graph families
• Injective colorings of sparse graphs
• List injective coloring of planar graphs with girth g 6
• Nordhaus-Gaddum-type relations of three graph coloring parameters

This page was built for publication: Some bounds on the injective chromatic number of graphs

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