ﻻ يوجد ملخص باللغة العربية
Let $G$ be a ${C_4, C_5}$-free planar graph with a list assignment $L$. Suppose a preferred color is given for some of the vertices. We prove that if all lists have size at least four, then there exists an $L$-coloring respecting at least a constant fraction of the preferences.
As usual, $P_n$ ($n geq 1$) denotes the path on $n$ vertices, and $C_n$ ($n geq 3$) denotes the cycle on $n$ vertices. For a family $mathcal{H}$ of graphs, we say that a graph $G$ is $mathcal{H}$-free if no induced subgraph of $G$ is isomorphic to an
Let $mathscr{G}$ be the class of plane graphs without triangles normally adjacent to $8^{-}$-cycles, without $4$-cycles normally adjacent to $6^{-}$-cycles, and without normally adjacent $5$-cycles. In this paper, it is showed that every graph in $ma
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
For which graphs $F$ is there a sparse $F$-counting lemma in $C_4$-free graphs? We are interested in identifying graphs $F$ with the property that, roughly speaking, if $G$ is an $n$-vertex $C_4$-free graph with on the order of $n^{3/2}$ edges, then
We introduce a new approach and prove that the maximum number of triangles in a $C_5$-free graph on $n$ vertices is at most $$(1 + o(1)) frac{1}{3 sqrt 2} n^{3/2}.$$ We also show a connection to $r$-uniform hypergraphs without (Berge) cycles of lengt