Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSize of edge-critical uniquely 3-colorable planar graphs
197
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic 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 $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.
rate research
Read More
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)leDelta$ for every proper subgraph $H$ of $G$. Vizing in 1968 conjectured that if $G$ is edge-$Delta$-critical, then $bar{d}geq Delta-1+ frac{3}{n}$. We show that $$ begin{displaystyle} avd ge begin{cases} 0.69241D-0.15658 quad,: mbox{ if } Deltageq 66, 0.69392D-0.20642quad;,mbox{ if } Delta=65, mbox{ and } 0.68706D+0.19815quad! quadmbox{if } 56leq Deltaleq64. end{cases} end{displaystyle} $$ This result improves the best known bound $frac{2}{3}(Delta +2)$ obtained by Woodall in 2007 for $Delta geq 56$. Additionally, Woodall constructed an infinite family of graphs showing his result cannot be improved by well-known Vizings Adjacency Lemma and other known edge-coloring techniques. To over come the barrier, we follow the recently developed recoloring technique of Tashkinov trees to expand Vizing fans technique to a larger class of trees.
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 )=Delta(G)+1$ and for any $ein E(G)$, $chi(G-e)=Delta(G)$. Let $G$ be an $n$-vertex $Delta$-critical graph. Vizing conjectured that $alpha(G)$, the independence number of $G$, is at most $frac{n}{2}$. The current best result on this conjecture, shown by Woodall, is that $alpha(G)<frac{3n}{5}$. We show that for any given $varepsilonin (0,1)$, there exist positive constants $d_0(varepsilon)$ and $D_0(varepsilon)$ such that if $G$ is an $n$-vertex $Delta$-critical graph with minimum degree at least $d_0$ and maximum degree at least $D_0$, then $alpha(G)<(frac{{1}}{2}+varepsilon)n$. In particular, we show that if $G$ is an $n$-vertex $Delta$-critical graph with minimum degree at least $d$ and $Delta(G)ge (d+2)^{5d+10}$, then [ alpha(G) < left. begin{cases} frac{7n}{12}, & text{if $d= 3$; } frac{4n}{7}, & text{if $d= 4$; } frac{d+2+sqrt[3]{(d-1)d}}{2d+4+sqrt[3]{(d-1)d}}n<frac{4n}{7}, & text{if $dge 19$. } end{cases} right. ]
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 three. In this paper, we study the structure and extreme edge density of $3$-flow-critical graphs. We apply structure properties to obtain lower and upper bounds on the density of $3$-flow-critical graphs, that is, for any $3$-flow-critical graph $G$ on $n$ vertices, $$frac{8n-2}{5}le |E(G)|le 4n-10,$$ where each equality holds if and only if $G$ is $K_4$. We conjecture that every $3$-flow-critical graph on $nge 7$ vertices has at most $3n-8$ edges, which would be tight if true. For planar graphs, the best possible density upper bound of $3$-flow-critical graphs on $n$ vertices is $frac{5n-8}{2}$, known from a result of Kostochka and Yancey (JCTB 2014) on vertex coloring $4$-critical graphs by duality.
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 triangles nor 5-, 6-, 9-cycles is 3-choosable. Liu et al. [Discrete Math. 342 (2019) 178--189] showed that every planar graph without 4-, 5-, 6- and 9-cycles is DP-3-colorable. In this paper, we show that every planar graph with neither adjacent triangles nor 5-, 6-, 9-cycles is DP-3-colorable, which generalizes these results. Yu et al. gave three Bordeaux-type results by showing that (i) every planar graph with the distance of triangles at least three and no 4-, 5-cycles is DP-3-colorable; (ii) every planar graph with the distance of triangles at least two and no 4-, 5-, 6-cycles is DP-3-colorable; (iii) every planar graph with the distance of triangles at least two and no 5-, 6-, 7-cycles is DP-3-colorable. We also give two Bordeaux-type results in the last section: (i) every plane graph with neither 5-, 6-, 8-cycles nor triangles at distance less than two is DP-3-colorable; (ii) every plane graph with neither 4-, 5-, 7-cycles nor triangles at distance less than two is DP-3-colorable.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
