Back to Search
Start Over
Injective choosability of subcubic planar graphs with girth 6
- Source :
- Discrete Mathematics. 340:2538-2549
- Publication Year :
- 2017
- Publisher :
- Elsevier BV, 2017.
-
Abstract
- An injective coloring of a graph $G$ is an assignment of colors to the vertices of $G$ so that any two vertices with a common neighbor have distinct colors. A graph $G$ is injectively $k$-choosable if for any list assignment $L$, where $|L(v)| \geq k$ for all $v \in V(G)$, $G$ has an injective $L$-coloring. Injective colorings have applications in the theory of error-correcting codes and are closely related to other notions of colorability. In this paper, we show that subcubic planar graphs with girth at least 6 are injectively 5-choosable. This strengthens a result of Lu\v{z}ar, \v{S}krekovski, and Tancer that subcubic planar graphs with girth at least 7 are injectively 5-colorable. Our result also improves several other results in particular cases.<br />Comment: 18 pages, 12 figures
- Subjects :
- Discrete mathematics
05C15, 05C10
010102 general mathematics
G.2.2
0102 computer and information sciences
01 natural sciences
Injective function
Graph
Theoretical Computer Science
Planar graph
Combinatorics
symbols.namesake
010201 computation theory & mathematics
Common neighbor
FOS: Mathematics
symbols
Mathematics - Combinatorics
Discrete Mathematics and Combinatorics
Combinatorics (math.CO)
0101 mathematics
Mathematics
Subjects
Details
- ISSN :
- 0012365X
- Volume :
- 340
- Database :
- OpenAIRE
- Journal :
- Discrete Mathematics
- Accession number :
- edsair.doi.dedup.....dc9537ea2821ecbe9035a376e9ae04b3