Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new user(4,2)-choosability of planar graphs with forbidden structures
81
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
All planar graphs are 4-colorable and 5-choosable, while some planar graphs are not 4-choosable. Determining which properties guarantee that a planar graph can be colored using lists of size four has received significant attention. In terms of constraining the structure of the graph, for any $ell in {3,4,5,6,7}$, a planar graph is 4-choosable if it is $ell$-cycle-free. In terms of constraining the list assignment, one refinement of $k$-choosability is choosability with separation. A graph is $(k,s)$-choosable if the graph is colorable from lists of size $k$ where adjacent vertices have at most $s$ common colors in their lists. Every planar graph is $(4,1)$-choosable, but there exist planar graphs that are not $(4,3)$-choosable. It is an open question whether planar graphs are always $(4,2)$-choosable. A chorded $ell$-cycle is an $ell$-cycle with one additional edge. We demonstrate for each $ell in {5,6,7}$ that a planar graph is $(4,2)$-choosable if it does not contain chorded $ell$-cycles.
rate research
Read More
Assume $ k $ is a positive integer, $ lambda={k_1,k_2,...,k_q} $ is a partition of $ k $ and $ G $ is a graph. A $lambda$-assignment of $ G $ is a $ k $-assignment $ L $ of $ G $ such that the colour set $ bigcup_{vin V(G)} L(v) $ can be partitioned into $ q $ subsets $ C_1cup C_2cupcdotscup C_q $ and for each vertex $ v $ of $ G $, $ |L(v)cap C_i|=k_i $. We say $ G $ is $lambda$-choosable if for each $lambda$-assignment $ L $ of $ G $, $ G $ is $ L $-colourable. In particular, if $ lambda={k} $, then $lambda$-choosable is the same as $ k $-choosable, if $ lambda={1, 1,...,1} $, then $lambda$-choosable is equivalent to $ k $-colourable. For the other partitions of $ k $ sandwiched between $ {k} $ and $ {1, 1,...,1} $ in terms of refinements, $lambda$-choosability reveals a complex hierarchy of colourability of graphs. Assume $lambda={k_1, ldots, k_q} $ is a partition of $ k $ and $lambda $ is a partition of $ kge k $. We write $ lambdale lambda $ if there is a partition $lambda={k_1, ldots, k_q}$ of $k$ with $k_i ge k_i$ for $i=1,2,ldots, q$ and $lambda$ is a refinement of $lambda$. It follows from the definition that if $ lambdale lambda $, then every $lambda$-choosable graph is $lambda$-choosable. It was proved in [X. Zhu, A refinement of choosability of graphs, J. Combin. Theory, Ser. B 141 (2020) 143 - 164] that the converse is also true. This paper strengthens this result and proves that for any $ lambda otle lambda $, for any integer $g$, there exists a graph of girth at least $g$ which is $lambda$-choosable but not $lambda$-choosable.
An (improper) graph colouring has defect $d$ if each monochromatic subgraph has maximum degree at most $d$, and has clustering $c$ if each monochromatic component has at most $c$ vertices. This paper studies defective and clustered list-colourings for graphs with given maximum average degree. We prove that every graph with maximum average degree less than $frac{2d+2}{d+2} k$ is $k$-choosable with defect $d$. This improves upon a similar result by Havet and Sereni [J. Graph Theory, 2006]. For clustered choosability of graphs with maximum average degree $m$, no $(1-epsilon)m$ bound on the number of colours was previously known. The above result with $d=1$ solves this problem. It implies that every graph with maximum average degree $m$ is $lfloor{frac{3}{4}m+1}rfloor$-choosable with clustering 2. This extends a result of Kopreski and Yu [Discrete Math., 2017] to the setting of choosability. We then prove two results about clustered choosability that explore the trade-off between the number of colours and the clustering. In particular, we prove that every graph with maximum average degree $m$ is $lfloor{frac{7}{10}m+1}rfloor$-choosable with clustering $9$, and is $lfloor{frac{2}{3}m+1}rfloor$-choosable with clustering $O(m)$. As an example, the later result implies that every biplanar graph is 8-choosable with bounded clustering. This is the best known result for the clustered version of the earth-moon problem. The results extend to the setting where we only consider the maximum average degree of subgraphs with at least some number of vertices. Several applications are presented.
List coloring generalizes graph coloring by requiring the color of a vertex to be selected from a list of colors specific to that vertex. One refinement of list coloring, called choosability with separation, requires that the intersection of adjacent lists is sufficiently small. We introduce a new refinement, called choosability with union separation, where we require that the union of adjacent lists is sufficiently large. For $t geq k$, a $(k,t)$-list assignment is a list assignment $L$ where $|L(v)| geq k$ for all vertices $v$ and $|L(u)cup L(v)| geq t$ for all edges $uv$. A graph is $(k,t)$-choosable if there is a proper coloring for every $(k,t)$-list assignment. We explore this concept through examples of graphs that are not $(k,t)$-choosable, demonstrating sparsity conditions that imply a graph is $(k,t)$-choosable, and proving that all planar graphs are $(3,11)$-choosable and $(4,9)$-choosable.
The vertex arboricity $a(G)$ of a graph $G$ is the minimum $k$ such that $V(G)$ can be partitioned into $k$ sets where each set induces a forest. For a planar graph $G$, it is known that $a(G)leq 3$. In two recent papers, it was proved that planar graphs without $k$-cycles for some $kin{3, 4, 5, 6, 7}$ have vertex arboricity at most 2. For a toroidal graph $G$, it is known that $a(G)leq 4$. Let us consider the following question: do toroidal graphs without $k$-cycles have vertex arboricity at most 2? It was known that the question is true for k=3, and recently, Zhang proved the question is true for $k=5$. Since a complete graph on 5 vertices is a toroidal graph without any $k$-cycles for $kgeq 6$ and has vertex arboricity at least three, the only unknown case was k=4. We solve this case in the affirmative; namely, we show that toroidal graphs without 4-cycles have vertex arboricity at most 2.
Given a graph $G$, the strong clique number of $G$, denoted $omega_S(G)$, is the maximum size of a set $S$ of edges such that every pair of edges in $S$ has distance at most $2$ in the line graph of $G$. As a relaxation of the renowned ErdH{o}s--Nev{s}etv{r}il conjecture regarding the strong chromatic index, Faudree et al. suggested investigating the strong clique number, and conjectured a quadratic upper bound in terms of the maximum degree. Recently, Cames van Batenburg, Kang, and Pirot conjectured a linear upper bound in terms of the maximum degree for graphs without even cycles. Namely, if $G$ is a $C_{2k}$-free graph, then $omega_S(G)leq (2k-1)Delta(G)-{2k-1choose 2}$, and if $G$ is a $C_{2k}$-free bipartite graph, then $omega_S(G)leq kDelta(G)-(k-1)$. We prove the second conjecture in a stronger form, by showing that forbidding all odd cycles is not necessary. To be precise, we show that a ${C_5, C_{2k}}$-free graph $G$ with $Delta(G)ge 1$ satisfies $omega_S(G)leq kDelta(G)-(k-1)$, when either $kgeq 4$ or $kin {2,3}$ and $G$ is also $C_3$-free. Regarding the first conjecture, we prove an upper bound that is off by the constant term. Namely, for $kgeq 3$, we prove that a $C_{2k}$-free graph $G$ with $Delta(G)ge 1$ satisfies $omega_S(G)leq (2k-1)Delta(G)+(2k-1)^2$. This improves some results of Cames van Batenburg, Kang, and Pirot.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
