Size of edge-critical uniquely 3-colorable planar graphs

DOI10.1016/J.DISC.2015.11.009MaRDI QIDQ906468zbMATH OpenOpenAlexFDO

Authors Zepeng Li, Zehui Shao, Jin Xu, Enqiang Zhu

Publication date 21 January 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

planar graphedge-critical graphuniquely 3-colorable planar graph

Mathematics Subject Classification ID

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

Abstract: A graph $G$ is emph{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 $einE(G)$. Mel'nikov and Steinberg [L. S. Mel'nikov, R. Steinberg, One counterexample for two conjectures on three coloring, Discrete Math. 20 (1977) 203-206] asked to find an exact upper bound for the number of edges in a edge-critical 3-colorable planar graph with $n$ vertices. In this paper, we give some properties of edge-critical uniquely 3-colorable planar graphs and prove that if $G$ is such a graph with $n(geq6)$ vertices, then $|E(G)|leqfrac52n-6$, which improves the upper bound $frac83n-frac173$ given by Matsumoto [N. Matsumoto, The size of edge-critical uniquely 3-colorable planar graphs, Electron. J. Combin. 20 (3) (2013) $$P49]. Furthermore, we find some edge-critical 3-colorable planar graphs which have $n(=10,12,14)$ vertices and $frac52n-7$ edges.

Recommendations

• The size of edge-critical uniquely 3-colorable planar graphs
• A note on uniquely 3-colourable planar graphs
• scientific article; zbMATH DE number 7288622
• Conjectures on uniquely 3-edge-colorable graphs
• scientific article; zbMATH DE number 1146229

Cites work

• An introduction to chromatic polynomials
• Graph theory
• On the coloring of signed graphs
• On uniquely 3-colorable planar graphs
• On uniquely colorable planar graphs
• One counterexample for two conjectures on three coloring
• The size of edge-critical uniquely 3-colorable planar graphs
• Uniquely colorable graphs
• Uniquely colorable graphs

Cited in

(6)

• The size of edge-critical uniquely 3-colorable planar graphs
• Three measures of edge-uncolorability
• scientific article; zbMATH DE number 7288622 (Why is no real title available?)
• scientific article; zbMATH DE number 7145382 (Why is no real title available?)
• A note on uniquely 3-colourable planar graphs
• Uniquely colorable graphs with equal chromatic and game chromatic numbers

This page was built for publication: Size of edge-critical uniquely 3-colorable planar graphs

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