More Like this

1. On Weak Flexibility in Planar Graphs

   https://doi.org/10.1007/s00373-022-02564-1  

   Lidický, Bernard ; Masařík, Tomáš ; Murphy, Kyle ; Zerbib, Shira ( December 2022 , Graphs and Combinatorics)

   Abstract Recently, Dvořák, Norin, and Postle introduced flexibility as an extension of list coloring on graphs (J Graph Theory 92(3):191–206, 2019, https://doi.org/10.1002/jgt.22447 ). In this new setting, each vertex v in some subset of V ( G ) has a request for a certain color r ( v ) in its list of colors L ( v ). The goal is to find an L coloring satisfying many, but not necessarily all, of the requests. The main studied question is whether there exists a universal constant $$\varepsilon >0$$ ε > 0 such that any graph G in some graph class $$\mathscr {C}$$ C satisfies at least $$\varepsilon$$ ε proportion of the requests. More formally, for $$k > 0$$ k > 0 the goal is to prove that for any graph $$G \in \mathscr {C}$$ G ∈ C on vertex set V , with any list assignment L of size k for each vertex, and for every $$R \subseteq V$$ R ⊆ V and a request vector $$(r(v): v\in R, ~r(v) \in L(v))$$ ( r ( v ) : v ∈ R , r ( v ) ∈ L ( v ) ) , there exists an L -coloring of G satisfying at least $$\varepsilon |R|$$ ε | R | requests. If this is true, then $$\mathscr {C}$$ C is called $$\varepsilon$$ ε - flexible for lists of size k . Choi, Clemen, Ferrara, Horn, Ma, and Masařík (Discrete Appl Math 306:20–132, 2022, https://doi.org/10.1016/j.dam.2021.09.021 ) introduced the notion of weak flexibility , where $$R = V$$ R = V . We further develop this direction by introducing a tool to handle weak flexibility. We demonstrate this new tool by showing that for every positive integer b there exists $$\varepsilon (b)>0$$ ε ( b ) > 0 so that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_b$$ K 4 , C 5 , C 6 , C 7 , B b is weakly $$\varepsilon (b)$$ ε ( b ) -flexible for lists of size 4 (here $$K_n$$ K n , $$C_n$$ C n and $$B_n$$ B n are the complete graph, a cycle, and a book on n vertices, respectively). We also show that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_5$$ K 4 , C 5 , C 6 , C 7 , B 5 is $$\varepsilon$$ ε -flexible for lists of size 4. The results are tight as these graph classes are not even 3-colorable. 

   more » « less
2. Concatenating Bipartite Graphs

   https://doi.org/10.37236/8451  

   Chudnovsky, Maria ; Hompe, Patrick ; Scott, Alex ; Seymour, Paul ; Spirkl, Sophie ( April 2022 , The Electronic Journal of Combinatorics)

   Let $x,y\in (0,1]$, and let $A,B,C$ be disjoint nonempty stable subsets of a graph $G$, where every vertex in $A$ has at least $x|B|$ neighbours in $B$, and every vertex in $B$ has at least $y|C|$ neighbours in $C$, and there are no edges between $A,C$. We denote by $\phi(x,y)$ the maximum $z$ such that, in all such graphs $G$, there is a vertex $v\in C$ that is joined to at least $z|A|$ vertices in $A$ by two-edge paths. This function has some interesting properties: we show, for instance, that $\phi(x,y)=\phi(y,x)$ for all $x,y$, and there is a discontinuity in $\phi(x,x)$ when $1/x$ is an integer. For $z=1/2, 2/3,1/3,3/4,2/5,3/5$, we try to find the (complicated) boundary between the set of pairs $(x,y)$ with $\phi(x,y)\ge z$ and the pairs with $\phi(x,y)1/3$. 

   more » « less
3. Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth

   https://doi.org/10.19086/aic.2022.6  

   Chudnovsky, Maria ; Abrishami, Tara ; Hajebi, Sepehr ; Spirkl, Sophie ( September 2022 , Advances in Combinatorics)

   A _theta_ is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family $\mathcal{H}$ of graphs, we say a graph $G$ is $\mathcal{H}$-_free_ if no induced subgraph of $G$ is isomorphic to a member of $\mathcal{H}$. We prove a conjecture of Sintiari and Trotignon, that there exists an absolute constant $c$ for which every (theta, triangle)-free graph $G$ has treewidth at most $c\log (|V(G)|)$. A construction by Sintiari and Trotignon shows that this bound is asymptotically best possible, and (theta, triangle)-free graphs comprise the first known hereditary class of graphs with arbitrarily large yet logarithmic treewidth.Our main result is in fact a generalization of the above conjecture, that treewidth is at most logarithmic in $|V(G)|$ for every graph $G$ excluding the so-called _three-path-configurations_ as well as a fixed complete graph. It follows that several NP-hard problems such as Stable Set, Vertex Cover, Dominating Set and $k$-Coloring (for fixed $k$) admit polynomial time algorithms in graphs excluding the three-path-configurations and a fixed complete graph. 

   more » « less
4. Complexity of Ck-Coloring in Hereditary Classes of Graphs

   Chudnovsky, M. ; Huang, S. ; Rzazewski, P. ; Spirkl, S. ; and Zhong, M. ( September 2019 , European Symposium on Algorithms)

   For a graph F, a graph G is F-free if it does not contain an induced subgraph isomorphic to F. For two graphs G and H, an H-coloring of G is a mapping f : V (G) → V (H) such that for every edge uv ∈ E(G) it holds that f(u)f(v) ∈ E(H). We are interested in the complexity of the problem H-Coloring, which asks for the existence of an H-coloring of an input graph G. In particular, we consider H-Coloring of F-free graphs, where F is a fixed graph and H is an odd cycle of length at least 5. This problem is closely related to the well known open problem of determining the complexity of 3-Coloring of Pt-free graphs. We show that for every odd k ≥ 5 the Ck-Coloring problem, even in the precoloring-extension variant, can be solved in polynomial time in P9-free graphs. On the other hand, we prove that the extension version of Ck-Coloring is NP-complete for F-free graphs whenever some component of F is not a subgraph of a subdivided claw. 

   more » « less
5. Almost Everywhere Behavior of Functions According to Partition Measures

   https://doi.org/10.1017/fms.2023.130  

   Chan, William ; Jackson, Stephen ; Trang, Nam ( January 2024 , Forum of Mathematics, Sigma)

   This paper will study almost everywhere behaviors of functions on partition spaces of cardinals possessing suitable partition properties. Almost everywhere continuity and monotonicity properties for functions on partition spaces will be established. These results will be applied to distinguish the cardinality of certain subsets of the power set of partition cardinals.

   The following summarizes the main results proved under suitable partition hypotheses.•

   If$\kappa $is a cardinal,$\epsilon < \kappa $,${\mathrm {cof}}(\epsilon ) = \omega $,$\kappa \rightarrow _* (\kappa )^{\epsilon \cdot \epsilon }_2$and$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$, then$\Phi $satisfies the almost everywhere short length continuity property: There is a club$C \subseteq \kappa $and a$\delta < \epsilon $so that for all$f,g \in [C]^\epsilon _*$, if$f \upharpoonright \delta = g \upharpoonright \delta $and$\sup (f) = \sup (g)$, then$\Phi (f) = \Phi (g)$.

   •

   If$\kappa $is a cardinal,$\epsilon $is countable,$\kappa \rightarrow _* (\kappa )^{\epsilon \cdot \epsilon }_2$holds and$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$, then$\Phi $satisfies the strong almost everywhere short length continuity property: There is a club$C \subseteq \kappa $and finitely many ordinals$\delta _0, ..., \delta _k \leq \epsilon $so that for all$f,g \in [C]^\epsilon _*$, if for all$0 \leq i \leq k$,$\sup (f \upharpoonright \delta _i) = \sup (g \upharpoonright \delta _i)$, then$\Phi (f) = \Phi (g)$.

   •

   If$\kappa $satisfies$\kappa \rightarrow _* (\kappa )^\kappa _2$,$\epsilon \leq \kappa $and$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$, then$\Phi $satisfies the almost everywhere monotonicity property: There is a club$C \subseteq \kappa $so that for all$f,g \in [C]^\epsilon _*$, if for all$\alpha < \epsilon $,$f(\alpha ) \leq g(\alpha )$, then$\Phi (f) \leq \Phi (g)$.

   •

   Suppose dependent choice ($\mathsf {DC}$),${\omega _1} \rightarrow _* ({\omega _1})^{\omega _1}_2$and the almost everywhere short length club uniformization principle for${\omega _1}$hold. Then every function$\Phi : [{\omega _1}]^{\omega _1}_* \rightarrow {\omega _1}$satisfies a finite continuity property with respect to closure points: Let$\mathfrak {C}_f$be the club of$\alpha < {\omega _1}$so that$\sup (f \upharpoonright \alpha ) = \alpha $. There is a club$C \subseteq {\omega _1}$and finitely many functions$\Upsilon _0, ..., \Upsilon _{n - 1} : [C]^{\omega _1}_* \rightarrow {\omega _1}$so that for all$f \in [C]^{\omega _1}_*$, for all$g \in [C]^{\omega _1}_*$, if$\mathfrak {C}_g = \mathfrak {C}_f$and for all$i < n$,$\sup (g \upharpoonright \Upsilon _i(f)) = \sup (f \upharpoonright \Upsilon _i(f))$, then$\Phi (g) = \Phi (f)$.

   •

   Suppose$\kappa $satisfies$\kappa \rightarrow _* (\kappa )^\epsilon _2$for all$\epsilon < \kappa $. For all$\chi < \kappa $,$[\kappa ]^{<\kappa }$does not inject into${}^\chi \mathrm {ON}$, the class of$\chi $-length sequences of ordinals, and therefore,$|[\kappa ]^\chi | < |[\kappa ]^{<\kappa }|$. As a consequence, under the axiom of determinacy$(\mathsf {AD})$, these two cardinality results hold when$\kappa $is one of the following weak or strong partition cardinals of determinacy:${\omega _1}$,$\omega _2$,$\boldsymbol {\delta }_n^1$(for all$1 \leq n < \omega $) and$\boldsymbol {\delta }^2_1$(assuming in addition$\mathsf {DC}_{\mathbb {R}}$).

    

   more » « less