Geodesic
The size of edge-critical uniquely 3-colorable planar graphs
Naoki Matsumoto1
1Yokohama National University
The electronic journal of combinatorics, Tome 20 (2013) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A graph $G$ is uniquely $k$-colorable if the chromatic number of $G$ is $k$ and $G$ has only one $k$-coloring up to permutation of the colors. A uniquely $k$-colorable graph $G$ is edge-critical if $G-e$ is not a uniquely $k$-colorable graph for any edge $e\in E(G)$. In this paper, we prove that if $G$ is an edge-critical uniquely $3$-colorable planar graph, then $|E(G)|\leq \frac{8}{3}|V(G)|-\frac{17}{3}$. On the other hand, there exists an infinite family of edge-critical uniquely 3-colorable planar graphs with $n$ vertices and $\frac{9}{4}n-6$ edges. Our result gives a first non-trivial upper bound for $|E(G)|$.
DOI : 10.37236/3228
Classification : 05C10, 05C15, 05C35
Mots-clés : graph theory, planar graphs, unique coloring

Naoki Matsumoto  1

1 Yokohama National University 
@article{10_37236_3228,
     author = {Naoki Matsumoto},
     title = {The size of edge-critical uniquely 3-colorable planar graphs},
     journal = {The electronic journal of combinatorics},
     year = {2013},
     volume = {20},
     number = {3},
     doi = {10.37236/3228},
     zbl = {1295.05090},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/3228/}
}
TY  - JOUR
AU  - Naoki Matsumoto
TI  - The size of edge-critical uniquely 3-colorable planar graphs
JO  - The electronic journal of combinatorics
PY  - 2013
VL  - 20
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/3228/
DO  - 10.37236/3228
ID  - 10_37236_3228
ER  - 
%0 Journal Article
%A Naoki Matsumoto
%T The size of edge-critical uniquely 3-colorable planar graphs
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/3228/
%R 10.37236/3228
%F 10_37236_3228
Naoki Matsumoto. The size of edge-critical uniquely 3-colorable planar graphs. The electronic journal of combinatorics, Tome 20 (2013) no. 3. doi: 10.37236/3228

Cité par Sources :