Zobrazeno 1 - 10
of 105
pro vyhledávání: '"Haxell, Penny"'
K\H onig's theorem says that the vertex cover number of every bipartite graph is at most its matching number (in fact they are equal since, trivially, the matching number is at most the vertex cover number). An equivalent formulation of K\H onig's th
Externí odkaz:
http://arxiv.org/abs/2409.18250
Autor:
Haxell, Penny, Wdowinski, Ronen
Given a graph $G$ and a partition $P$ of its vertex set, an independent transversal (IT) is an independent set of $G$ that contains one vertex from each block in $P$. Various sufficient conditions for the existence of an IT have been established, and
Externí odkaz:
http://arxiv.org/abs/2309.12150
We say that a signed graph is $k$-critical if it is not $k$-colorable but every one of its proper subgraphs is $k$-colorable. Using the definition of colorability due to Naserasr, Wang, and Zhu that extends the notion of circular colorability, we pro
Externí odkaz:
http://arxiv.org/abs/2309.04450
Given a bipartite graph $H=(V=V_A\cup V_B,E)$ in which any vertex in $V_A$ (resp.~$V_B$) has degree at most $D_A$ (resp.~$D_B$), suppose there is a partition of $V$ that is a refinement of the bipartition $V_A\cup V_B$ such that the parts in $V_A$ (r
Externí odkaz:
http://arxiv.org/abs/2308.14778
Autor:
Haxell, Penny, Wdowinski, Ronen
An \emph{independent transversal} (IT) in a graph $G$ with a given vertex partition $P$ is an independent set of vertices of $G$ (i.e. it induces no edges), that consists of one vertex from each part (\emph{block}) of $P$. Over the years, various cri
Externí odkaz:
http://arxiv.org/abs/2305.10595
Autor:
Haxell, Penny, Szabó, Tibor
In the max-min allocation problem a set $P$ of players are to be allocated disjoint subsets of a set $R$ of indivisible resources, such that the minimum utility among all players is maximized. We study the restricted variant, also known as the Santa
Externí odkaz:
http://arxiv.org/abs/2202.01143
Autor:
Haxell, Penny, MacDonald, Colter
Publikováno v:
In Discrete Mathematics November 2023 346(11)
Publikováno v:
ACM Transactions on Algorithms 18(1), Article #1 (2021)
An independent transversal (IT) in a graph with a given vertex partition is an independent set consisting of one vertex in each partition class. Several sufficient conditions are known for the existence of an IT in a given graph with a given vertex p
Externí odkaz:
http://arxiv.org/abs/1907.00033
Autor:
Graf, Alessandra, Haxell, Penny
Publikováno v:
Combinator. Probab. Comp. 29 (2020) 780-806
We give an efficient algorithm that, given a graph $G$ and a partition $V_1,\ldots,V_m$ of its vertex set, finds either an independent transversal (an independent set $\{v_1,\ldots,v_m\}$ in $G$ such that $v_i\in V_i$ for each $i$), or a subset $\mat
Externí odkaz:
http://arxiv.org/abs/1811.02687
In the 70s, Goldberg, and independently Seymour, conjectured that for any multigraph $G$, the chromatic index $\chi'(G)$ satisfies $\chi'(G)\leq \max \{\Delta(G)+1, \lceil\rho(G)\rceil\}$, where $\rho(G)=\max \{\frac {e(G[S])}{\lfloor |S|/2\rfloor} \
Externí odkaz:
http://arxiv.org/abs/1803.00908