Independent domination of graphs with bounded maximum degree

Autor: Eun-Kyung Cho, Jinha Kim, Minki Kim, Sang-il Oum

Publikováno v: Journal of Combinatorial Theory, Series B. 158:341-352

An independent dominating set of a graph, also known as a maximal independent set, is a set $S$ of pairwise non-adjacent vertices such that every vertex not in $S$ is adjacent to some vertex in $S$. We prove that for $\Delta=4$ or $\Delta\ge 6$, ever

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a9091cf12ec75063c9775cec322815ad
https://doi.org/10.1016/j.jctb.2022.10.004

Problems

Autor: Niculescu, Constantin P., Lee, Ho-joo, Florin, Jon, Eynden, Charles Vanden, Bencze, Mihaly, Chao, Wu Wei, Sang-il, Oum, Rey, Joaquin Gomez, Andreoli, Michael H., Chapman, Robin, Penrice, Stephen G., Spellman, Dennis, Wardlaw, William P., Smith, John H., Alkan, Emre, Haywood, Joel D.

Publikováno v: Mathematics Magazine, 2000 Feb 01. 73(1), 62-70.

Externí odkaz: https://www.jstor.org/stable/2691498

The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs

Autor: Jungho Ahn, Seonghyuk Im, Sang-il Oum

A proper coloring of a graph is \emph{proper conflict-free} if every non-isolated vertex $v$ has a neighbor whose color is unique in the neighborhood of $v$. A proper coloring of a graph is \emph{odd} if for every non-isolated vertex $v$, there is a

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e5be4054d453bc8699e4211425da6dcc
http://arxiv.org/abs/2208.08330

Tree Pivot-Minors and Linear Rank-Width

Autor: Konrad K. Dabrowski, François Dross, Jisu Jeong, Mamadou M. Kanté, O-joung Kwon, Sang-il Oum, Daniël Paulusma

Publikováno v: Scopus-Elsevier
SIAM journal on discrete mathematics, 2021, Vol.35(4), pp.2922-2945 [Peer Reviewed Journal]
SIAM Journal on Discrete Mathematics
SIAM Journal on Discrete Mathematics, 2021, 35 (4), pp.2922-2945. ⟨10.1137/21M1402339⟩

Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree~$T$, the class of graphs that do not contain $T$ as a minor has bounded path-width.

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::15133ded7c08377859a9c00d2d90405d
https://eprints.whiterose.ac.uk/177573/1/treepivot.pdf

Improper colouring of graphs with no odd clique minor

Autor: Dong Yeap Kang, Sang-il Oum

Publikováno v: Combinatorics, Probability and Computing. 28:740-754

As a strengthening of Hadwiger's conjecture, Gerards and Seymour conjectured that every graph with no odd $K_t$ minor is $(t-1)$-colorable. We prove two weaker variants of this conjecture. Firstly, we show that for each $t \geq 2$, every graph with n

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::88b0f44932550264ba71b2ae78bd3592
https://doi.org/10.1017/s0963548318000548