ﻻ يوجد ملخص باللغة العربية
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 $ein E(G)$. Melnikov and Steinberg [L. S. Melnikov, 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)|leq frac{5}{2}n-6 $, which improves the upper bound $frac{8}{3}n-frac{17}{3}$ 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 $frac{5}{2}n-7$ edges.
Let $G=(V,E)$ be a $tau$-critical graph with $tau(G)=t$. ErdH{o}s and Gallai proved that $|V|leq 2t$ and the bound $|E|leq {t+1choose 2}$ was obtained by ErdH{o}s, Hajnal and Moon. We give here the sharp combined bound $|E|+|V|leq {t+2choose 2}$ and find all graphs with equality.
Given a graph $G$, denote by $Delta$, $bar{d}$ and $chi^prime$ the maximum degree, the average degree and the chromatic index of $G$, respectively. A simple graph $G$ is called {it edge-$Delta$-critical} if $chi^prime(G)=Delta+1$ and $chi^prime(H)leD
Let $G$ be a simple graph with maximum degree $Delta(G)$ and chromatic index $chi(G)$. A classic result of Vizing indicates that either $chi(G )=Delta(G)$ or $chi(G )=Delta(G)+1$. The graph $G$ is called $Delta$-critical if $G$ is connected, $chi(G )
A bridgeless graph $G$ is called $3$-flow-critical if it does not admit a nowhere-zero $3$-flow, but $G/e$ has for any $ein E(G)$. Tuttes $3$-flow conjecture can be equivalently stated as that every $3$-flow-critical graph contains a vertex of degree
DP-coloring is a generalization of list coloring, which was introduced by Dvov{r}{a}k and Postle [J. Combin. Theory Ser. B 129 (2018) 38--54]. Zhang [Inform. Process. Lett. 113 (9) (2013) 354--356] showed that every planar graph with neither adjacent