Originators: G. Wegner; Geňa Hahn, André Raspaud, and Weifan Wang (presented by Douglas West - REGS 2007)
Definitions: A k-coloring of the vertices of a graph is an injective coloring if for every vertex v, the neighbors of v receive distinct colors. The injective chromatic number χi(G) is the least k such that G has an injective k-coloring. The square of a graph G is the graph G² with the same vertex set as G in which vertices are adjacent if their distance in G is at most 2 The maximum average degree mad(G) of a graph G is the maximum, over all subgraphs, of the average vertex degree.
Background: An injective coloring need not be a proper coloring; indeed, the injective chromatic number of the Petersen graph is 5, with each color class inducing K2. Hahn-Kratochvil-Siran-Sotteau [HKSS] introduced χi(G) and noted for a graph with maximum degree d that d ≤ χi(G) ≤ χ(G²)≤ d²-d+1. Indeed, χi(G) equals the chromatic number of the "common neighbor graph", the graph on vertex set V(G) where vertices are adjacent if they have a common neighbor in G.
The upper bound d²-d+1 holds with equality if and only if G is the incidence graph of a projective plane of order d-1 [HKSS]. The lower bound holds with equality for a d-regular graph only if d divides the number of vertices [HKSS]. [HKSS] also discusses injective coloring of cartesian products, particularly hypercubes.
The conjectured extremal values for χi(G) for planar graphs (in terms of the maximum degree d) are similar to those for χ(G²).
Conjecture 1
(Wegner [W]): If G is planar with maximum degree d, then
χ(G²)≤7 when d=3,
χ(G²)≤d+5 when 4≤ d≤ 7, and
χ(G²)≤(3d/2)+1 when d≥ 8.
Comments: For planar graphs with girth g and maximum degree d, Dvořák-Král'-Nejedlý-Škrekovski [DKNS] proved that χ(G²)≤d+1 when g≥7 and d is sufficiently large, and χ(G²)≤d+2 when g=6. Molloy-Salavatipour [MS] proved that χ(G²)&le(5d/3)+78. For d=3, Montassier-Raspaud [MR] proved that χ(G²)≤5 if g≥14 and χ(G²)≤6 if g≥10.
Conjecture 2 (Hahn-Raspaud-Wang [HRW]): If G is planar with maximum degree d, then χi(G)≤ ⌈3d/2⌉.
Comments: Doyon-Hahn-Raspaud [DHR] proved that χi(G)≤ ⌈3d/2⌉ whenever G does not have K4 as a minor.
Question 3: What bounds can be given on the injective chromatic number when mad(G) is bounded?
Comments:
Doyon-Hahn-Raspaud [DHR] proved bounds on χi(G) in terms
of the maximum degree d when mad(G) is bounded:
If mad(G)<14/5, then χi(G)≤ d+3,
If mad(G)< 3, then χi(G)≤ d+4,
and
If mad(G)<10/3, then χi(G)≤ d+8.
Since mad(G)<2g/(g-2) when G is a planar graph with girth
g, these provide the upper bounds d+3, d+4, d+8
for planar graphs with girths 7,6,5, respectively, and maximum degree
d. These bounds have been improved in various ways by Lužar,
Škrekovski, and Tancer [LST]:
If g≥19, then χi(G)≤ d.
If g≥10, then χi(G)≤ d+1.
If g≥5 and d is large, then
χi(G)≤ d+4.
If g≥7 and d=3, then χi(G)≤ 5.
Problem 4: Find classes on which χi is computable in polynomial time.
Comments: [HKSS] showed that computing χi is NP-hard in general. It is easy for trees and cycles and probably is not much harder for cacti. What about outerplanar graphs?
References:
[DHR] A. Doyon, G. Hahn, A. Raspaud;
On the injective chromatic number of sparse graphs, preprint 2005.
[DKNS] Z. Dvořák, D. Král', P. Nejedlý,
R. Škrekovski;
Coloring squares of planar graphs with girth six,
European J. Combin. 29 (2008), 838--849.
[HKSS] Hahn, Geňa; Kratochvîl, Jan; Širáň, Jozef;
Sotteau, Dominique; On the injective chromatic number of graphs.
Discrete Math. 256 (2002), no. 1-2, 179--192.
[HRW] G. Hahn, A. Raspaud, W. Wang;
On the injective coloring of K4-minor free graphs,
preprint 2006.
[LST] B. Lužar, R. Škrekovski, and M. Tancer;
Injective colorings of planar graphs with few colors, preprint 2008:
kam.mff.cuni.cz/~kamserie/serie/clanky/2006/s798.ps, to appear in
Discrete Math.
[MS] M. Molloy and M. R. Salavatipour; A bound on the chromatic number of the
square of a planar graph,
J. Combin. Th. (B) 94 (2005), 189-213.
[MR] M. Montassier and A. Raspaud; A note on 2-facial coloring of plane graphs,
Technical Report RR-1341-05, LaBRI (2005).
[W] G. Wegner, Graphs with given diameter and a coloring problem,
Technical Report, University of Dortmund (1977).
Posted July 2008