Size of edge-critical uniquely 3-colorable planar graphs

DOI10.1016/J.DISC.2015.11.009zbMATH Open1329.05085arXiv1312.7495OpenAlexW1516923601MaRDI QIDQ906468FDOQ906468

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

Publication date: 21 January 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (6)

• The size of edge-critical uniquely 3-colorable planar graphs
• Three measures of edge-uncolorability
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)