Zobrazeno 1 - 10
of 27
pro vyhledávání: '"Hehui Wu"'
Autor:
BOJAN MOHAR, HEHUI WU
Publikováno v:
Forum of Mathematics, Sigma, Vol 4 (2016)
The dichromatic number of a graph $G$ is the maximum integer $k$ such that there exists an orientation of the edges of $G$ such that for every partition of the vertices into fewer than $k$ parts, at least one of the parts must contain a directed
Externí odkaz:
https://doaj.org/article/c365064a067649b282527c431ed7305c
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol DMTCS Proceedings vol. AE,..., Iss Proceedings (2005)
Thomassen conjectured that every $4$-connected line graph is hamiltonian. A vertex cut $X$ of $G$ is essential if $G-X$ has at least two nontrivial components. We prove that every $3$-connected, essentially $11$-connected line graph is hamiltonian. U
Externí odkaz:
https://doaj.org/article/7ca86edf3b374192ad4b5c7225e1c4ac
Publikováno v:
Journal of Combinatorial Theory, Series B. 161:63-85
The proper chromatic number $\Vec{\chi}(G)$ of a graph $G$ is the minimum $k$ such that there exists an orientation of the edges of $G$ with all vertex-outdegrees at most $k$ and such that for any adjacent vertices, the outdegrees are different. Two
Publikováno v:
The Electronic Journal of Combinatorics. 29
Let the crown $C_{13}$ be the linear $3$-graph on $9$ vertices $\{a,b,c,d,e,f,g,h,i\}$ with edges $$E = \{\{a,b,c\}, \{a, d,e\}, \{b, f, g\}, \{c, h,i\}\}.$$ Proving a conjecture of Gyárfás et. al., we show that for any crown-free linear $3$-graph
Letters $x$ and $y$ alternate in a word $w$ if after deleting in $w$ all letters but the copies of $x$ and $y$ we either obtain a word $xyxy\cdots$ (of even or odd length) or a word $yxyx\cdots$ (of even or odd length). A graph $G=(V,E)$ is word-repr
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::844d50df364fa9c7cb6c2a4c7b47a236
https://strathprints.strath.ac.uk/73875/1/Kitaev_etal_JC_2020_Word_representability_of_split_graphs.pdf
https://strathprints.strath.ac.uk/73875/1/Kitaev_etal_JC_2020_Word_representability_of_split_graphs.pdf
Autor:
Bojan Mohar, Hehui Wu
Publikováno v:
The Art of Discrete and Applied Mathematics. 6:#P2.11
Publikováno v:
Journal of Combinatorial Theory, Series B
Journal of Combinatorial Theory, Series B, Elsevier, 2019, 138, pp.166-171. ⟨10.1016/j.jctb.2019.01.005⟩
Journal of Combinatorial Theory, Series B, 2019, 138, pp.166-171. ⟨10.1016/j.jctb.2019.01.005⟩
Journal of Combinatorial Theory, Series B, Elsevier, 2019, 138, pp.166-171. ⟨10.1016/j.jctb.2019.01.005⟩
Journal of Combinatorial Theory, Series B, 2019, 138, pp.166-171. ⟨10.1016/j.jctb.2019.01.005⟩
The \emph{chromatic number} of a directed graph $D$ is the minimum number of colors needed to color the vertices of $D$ such that each color class of $D$ induces an acyclic subdigraph. Thus, the chromatic number of a tournament $T$ is the minimum num
Publikováno v:
Combinatorica
Combinatorica, Springer Verlag, 2020, ⟨10.1007/s00493-020-4223-9⟩
Combinatorica, Springer Verlag, 2020, ⟨10.1007/s00493-020-4223-9⟩
The Hall ratio of a graph G is the maximum of |V(H)|/α(H) over all subgraphs H of G. It is easy to see that the Hall ratio of a graph is a lower bound for the fractional chromatic number. It has been asked whether conversely, the fractional chromati
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::16d2d091a150ee9f7051f57d413cf408
https://hal.inria.fr/hal-03039315
https://hal.inria.fr/hal-03039315
Publikováno v:
Journal of Combinatorial Theory, Series B. 126:162-174
For a graph H let c ( H ) denote the supremum of | E ( G ) | / | V ( G ) | taken over all non-null graphs G not containing H as a minor. We show that c ( H ) ≤ | V ( H ) | + comp ( H ) 2 − 1 , when H is a union of cycles. This verifies a conjectu
Autor:
Bojan Mohar, Hehui Wu
It is well known that a random subgraph of the complete graph $K_n$ has chromatic number $\Theta(n/\log n)$ w.h.p. Boris Bukh asked whether the same holds for a random subgraph of any $n$-chromatic graph, at least in expectation. In this paper it is
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::130490b4139577ccffba07de9ae83d0e