Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userChoosability with union separation
73
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
Three intersection theorems are proved. First, we determine the size of the largest set system, where the system of the pairwise unions is l-intersecting. Then we investigate set systems where the union of any s sets intersect the union of any t sets. The maximal size of such a set system is determined exactly if s+t<5, and asymptotically if s+t>4. Finally, we exactly determine the maximal size of a k-uniform set system that has the above described (s,t)-union-intersecting property, for large enough n.
In this very short note, we point out that the average overlap density of a union-closed family $mathcal{F}$ of subsets of ${1,2,ldots,n}$ may be as small as $Theta((log log |mathcal{F}|)/(log |mathcal{F}|))$, for infinitely many positive integers $n$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
