Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe strong fractional choice number of $3$-choice critical graphs
125
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A graph $G$ is called $3$-choice critical if $G$ is not $2$-choosable but any proper subgraph is $2$-choosable. A graph $G$ is strongly fractional $r$-choosable if $G$ is $(a,b)$-choosable for all positive integers $a,b$ for which $a/b ge r$. The strong fractional choice number of $G$ is $ch_f^s(G) = inf {r: G $ is strongly fractional $r$-choosable$}$. This paper determines the strong fractional choice number of all $3$-choice critical graphs.
rate research
Read More
A graph $G$ is called $3$-choice critical if $G$ is not $2$-choosable but any proper subgraph is $2$-choosable. A characterization of $3$-choice critical graphs was given by Voigt in [On list Colourings and Choosability of Graphs, Habilitationsschrift, Tu Ilmenau(1998)]. Voigt conjectured that if $G$ is a bipartite $3$-choice critical graph, then $G$ is $(4m, 2m)$-choosable for every integer $m$. This conjecture was disproved by Meng, Puleo and Zhu in [On (4, 2)-Choosable Graphs, Journal of Graph Theory 85(2):412-428(2017)]. They showed that if $G=Theta_{r,s,t}$ where $r,s,t$ have the same parity and $min{r,s,t} ge 3$, or $G=Theta_{2,2,2,2p}$ with $p ge 2$, then $G$ is bipartite $3$-choice critical, but not $(4,2)$-choosable. On the other hand, all the other bipartite 3-choice critical graphs are $(4,2)$-choosable. This paper strengthens the result of Meng, Puleo and Zhu and shows that all the other bipartite $3$-choice critical graphs are $(4m,2m)$-choosable for every integer $m$.
In this short note, we show that for any $epsilon >0$ and $k<n^{0.5-epsilon}$ the choice number of the Kneser graph $KG_{n,k}$ is $Theta (nlog n)$.
This is a survey paper on rainbow sets (another name for ``choice functions). The main theme is the distinction between two types of choice functions: those having a large (in the sense of belonging to some specified filter, namely closed up set of sets) image, and those that have a large domain and small image, where ``smallness means belonging to some specified complex (a closed-down set). The paper contains some new results: (1) theorems on scrambl
A social choice correspondence satisfies balancedness if, for every pair of alternatives, x and y, and every pair of individuals, i and j, whenever a profile has x adjacent to but just above y for individual i while individual j has y adjacent to but just above x, then only switching x and y in the orderings for both of those two individuals leaves the choice set unchanged. We show how the balancedness condition interacts with other social choice properties, especially tops-only. We also use balancedness to characterize the Borda rule (for a fixed number of voters) within the class of scoring rules.
We prove a common generalization of two results, one on rainbow fractional matchings and one on rainbow sets in the intersection of two matroids: Given $d = r lceil k rceil - r + 1$ functions of size (=sum of values) $k$ that are all independent in each of $r$ given matroids, there exists a rainbow set of $supp(f_i)$, $i leq d$, supporting a function with the same properties.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
