Zobrazeno 1 - 10
of 150
pro vyhledávání: '"Kierstead, H. A."'
If $L$ is a list assignment of $r$ colors to each vertex of an $n$-vertex graph $G$, then an equitable $L$-coloring of $G$ is a proper coloring of vertices of $G$ from their lists such that no color is used more than $\lceil n/r\rceil$ times. A graph
Externí odkaz:
http://arxiv.org/abs/2309.00989
Autor:
Biró, Csaba, Hamburger, Peter, Kierstead, H. A., Pór, Attila, Trotter, William T., Wang, Ruidong
Previously, Erd\H{o}s, Kierstead and Trotter investigated the dimension of random height~$2$ partially ordered sets. Their research was motivated primarily by two goals: (1)~analyzing the relative tightness of the F\"{u}redi-Kahn upper bounds on dime
Externí odkaz:
http://arxiv.org/abs/2003.07935
Publikováno v:
J. Graph Theory, 99(2):251-277, February 2022
A graph $G$ is $d$-degenerate if every non-null subgraph of $G$ has a vertex of degree at most $d$. We prove that every $n$-vertex planar graph has a $3$-degenerate induced subgraph of order at least $3n/4$.
Comment: 28 pages, 12 figures
Comment: 28 pages, 12 figures
Externí odkaz:
http://arxiv.org/abs/2002.07984
Autor:
Heuvel, Jan van den, Kierstead, H. A.
The generalized coloring numbers col_r(G) (also denoted by scol_r(G)) and wcol_r(G) of a graph G were introduced by Kierstead and Yang as a generalization of the usual coloring number, and have found important theoretical and algorithmic applications
Externí odkaz:
http://arxiv.org/abs/1907.12149
The weak $r$-coloring numbers $wcol_r(G)$ of a graph $G$ were introduced by the first two authors as a generalization of the usual coloring number $col(G)$, and have since found interesting theoretical and algorithmic applications. This has motivated
Externí odkaz:
http://arxiv.org/abs/1907.10962
For any graph $G=(V,E)$ and positive integer $p$, the exact distance-$p$ graph $G^{[\natural p]}$ is the graph with vertex set $V$, which has an edge between vertices $x$ and $y$ if and only if $x$ and $y$ have distance $p$ in $G$. For odd $p$, Ne\v{
Externí odkaz:
http://arxiv.org/abs/1612.02160
In 1963, Corr\'adi and Hajnal proved that for all $k\geq1$ and $n\geq3k$, every graph $G$ on $n$ vertices with minimum degree $\delta(G)\geq2k$ contains $k$ disjoint cycles. The bound $\delta(G) \geq 2k$ is sharp. Here we characterize those graphs wi
Externí odkaz:
http://arxiv.org/abs/1601.03791
First-fit is the online graph coloring algorithm that considers vertices one at a time in some order and assigns each vertex the least positive integer not used already on a neighbor. The maximum number of colors used by first-fit on graph G over all
Externí odkaz:
http://arxiv.org/abs/1506.00192
Let $\mathrm{ch}(G)$ denote the choice number of a graph $G$, and let $K_{s*k}$ be the complete $k$-partite graph with $s$ vertices in each part. Erd\H{o}s, Rubin, and Taylor showed that $\mathrm{ch}( K_{2*k})=k$, and suggested the problem of determi
Externí odkaz:
http://arxiv.org/abs/1407.3817
In 1963, Corr\'adi and Hajnal proved that for all $k \ge 1$ and $n \ge 3k$, every (simple) graph on n vertices with minimum degree at least 2k contains k disjoint cycles. The same year, Dirac described the 3-connected multigraphs not containing two d
Externí odkaz:
http://arxiv.org/abs/1406.7453