BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Ringi Kim

Ringi Kim appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.CO

Catalog footprint

What is connected

9works
1topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

9 published item(s)

preprint2020arXiv

Decomposing planar graphs into graphs with degree restrictions

Given a graph $G$, a decomposition of $G$ is a partition of its edges. A graph is $(d, h)$-decomposable if its edge set can be partitioned into a $d$-degenerate graph and a graph with maximum degree at most $h$. For $d \le 4$, we are interested in the minimum integer $h_d$ such that every planar graph is $(d,h_d)$-decomposable. It was known that $h_3 \le 4$, $h_2\le 8$, and $h_1 = \infty$. This paper proves that $h_4=1, h_3=2$, and $4 \le h_2 \le 6$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The strong clique number of graphs with forbidden cycles

Given a graph $G$, the strong clique number of $G$, denoted $ω_S(G)$, is the maximum size of a set $S$ of edges such that every pair of edges in $S$ has distance at most $2$ in the line graph of $G$. As a relaxation of the renowned Erdős--Nešetřil conjecture regarding the strong chromatic index, Faudree et al. suggested investigating the strong clique number, and conjectured a quadratic upper bound in terms of the maximum degree. Recently, Cames van Batenburg, Kang, and Pirot conjectured a linear upper bound in terms of the maximum degree for graphs without even cycles. Namely, if $G$ is a $C_{2k}$-free graph, then $ω_S(G)\leq (2k-1)Δ(G)-{2k-1\choose 2}$, and if $G$ is a $C_{2k}$-free bipartite graph, then $ω_S(G)\leq kΔ(G)-(k-1)$. We prove the second conjecture in a stronger form, by showing that forbidding all odd cycles is not necessary. To be precise, we show that a $\{C_5, C_{2k}\}$-free graph $G$ with $Δ(G)\ge 1$ satisfies $ω_S(G)\leq kΔ(G)-(k-1)$, when either $k\geq 4$ or $k\in \{2,3\}$ and $G$ is also $C_3$-free. Regarding the first conjecture, we prove an upper bound that is off by the constant term. Namely, for $k\geq 3$, we prove that a $C_{2k}$-free graph $G$ with $Δ(G)\ge 1$ satisfies $ω_S(G)\leq (2k-1)Δ(G)+(2k-1)^2$. This improves some results of Cames van Batenburg, Kang, and Pirot.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Chromatic index determined by fractional chromatic index

Given a graph $G$ possibly with multiple edges but no loops, denote by $Δ$ the {\it maximum degree}, $μ$ the {\it multiplicity}, $χ'$ the {\it chromatic index} and $χ_f'$ the {\it fractional chromatic index} of $G$, respectively. It is known that $Δ\le χ_f' \le χ' \le Δ+ μ$, where the upper bound is a classic result of Vizing. While deciding the exact value of $χ'$ is a classic NP-complete problem, the computing of $χ_f'$ is in polynomial time. In fact, it is shown that if $χ_f' > Δ$ then $χ_f'= \max \frac{|E(H)|}{\lfloor |V(H)|/2\rfloor}$, where the maximality is over all induced subgraphs $H$ of $G$. Gupta\,(1967), Goldberg\,(1973), Andersen\,(1977), and Seymour\,(1979) conjectured that $χ'=\lceilχ_f'\rceil$ if $χ'\ge Δ+2$, which is commonly referred as Goldberg's conjecture. In this paper, we show that if $χ' >Δ+\sqrt[3]{Δ/2}$ then $χ'=\lceilχ_f'\rceil$. The previous best known result is for graphs with $χ'> Δ+\sqrt{Δ/2}$ obtained by Scheide, and by Chen, Yu and Zang, independently. It has been shown that Goldberg's conjecture is equivalent to the following conjecture of Jakobsen: {\it For any positive integer $m$ with $m\ge 3$, every graph $G$ with $χ'>\frac{m}{m-1}Δ+\frac{m-3}{m-1}$ satisfies $χ'=\lceilχ_f'\rceil$.} Jakobsen's conjecture has been verified for $m$ up to 15 by various researchers in the last four decades. We show that it is true for $m\le 23$. Moreover, we show that Goldberg's conjecture holds for graphs $G$ with $Δ\leq 23$ or $|V(G)|\leq 23$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Cycles with two blocks in $k$-chromatic digraphs

Let $k$ and $\ell$ be positive integers. A cycle with two blocks $c(k,\ell)$ is an oriented cycle which consists of two internally (vertex) disjoint directed paths of lengths at least $k$ and $\ell$, respectively, from a vertex to another one. A problem of Addario-Berry, Havet and Thomassé (2007) asked if, given positive integers $k$ and $\ell$ such that $k+\ell\ge 4$, any strongly connected digraph $D$ containing no $c(k,\ell)$ has chromatic number at most $k+\ell-1$. In this paper, we show that such digraph $D$ has chromatic number at most $O((k+\ell)^2)$, improving the previous upper bound $O((k+\ell)^4)$ obtained by Cohen, Havet, Lochet and Nisse (2016). In fact, we are able to find a digraph which shows that the answer to the above problem is no. We also show that if in addition $D$ is Hamiltonian, then its underlying simple graph is $(k+\ell-1)$-degenerate and thus the chromatic number of $D$ is at most $k+\ell$, which is tight.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Tree-chromatic number is not equal to path-chromatic number

For a graph $G$ and a tree-decomposition $(T, \mathcal{B})$ of $G$, the chromatic number of $(T, \mathcal{B})$ is the maximum of $χ(G[B])$, taken over all bags $B \in \mathcal{B}$. The tree-chromatic number of $G$ is the minimum chromatic number of all tree-decompositions $(T, \mathcal{B})$ of $G$. The path-chromatic number of $G$ is defined analogously. In this paper, we introduce an operation that always increases the path-chromatic number of a graph. As an easy corollary of our construction, we obtain an infinite family of graphs whose path-chromatic number and tree-chromatic number are different. This settles a question of Seymour. Our results also imply that the path-chromatic numbers of the Mycielski graphs are unbounded.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Unavoidable induced subgraphs in large graphs with no homogeneous sets

A homogeneous set of an $n$-vertex graph is a set $X$ of vertices ($2\le |X|\le n-1$) such that every vertex not in $X$ is either complete or anticomplete to $X$. A graph is called prime if it has no homogeneous set. A chain of length $t$ is a sequence of $t+1$ vertices such that for every vertex in the sequence except the first one, its immediate predecessor is its unique neighbor or its unique non-neighbor among all of its predecessors. We prove that for all $n$, there exists $N$ such that every prime graph with at least $N$ vertices contains one of the following graphs or their complements as an induced subgraph: (1) the graph obtained from $K_{1,n}$ by subdividing every edge once, (2) the line graph of $K_{2,n}$, (3) the line graph of the graph in (1), (4) the half-graph of height $n$, (5) a prime graph induced by a chain of length $n$, (6) two particular graphs obtained from the half-graph of height $n$ by making one side a clique and adding one vertex.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Disjoint dijoins

A dijoin in a digraph is a set of edges meeting every directed cut. D. R. Woodall conjectured in 1976 that if G is a digraph, and every directed cut of G has at least k edges, then there are k pairwise disjoint dijoins. This remains open, but a capacitated version is known to be false. In particular, A. Schrijver gave a digraph G and a subset S of its edge-set, such that every directed cut contains at least two edges in S, and yet there do not exist two disjoint dijoins included in S. In Schrijver's example, G is planar, and the subdigraph formed by the edges in S consists of three disjoint paths. We conjecture that when k = 2, the disconnectedness of S is crucial: more precisely, that if G is a digraph, and S is a subset of the edges of G that forms a connected subdigraph (as an undirected graph), and every directed cut of G contains at least two edges in S, then we can partition S into two dijoins. We prove this in two special cases: when G is planar, and when the subdigraph formed by the edges in S is a subdivision of a caterpillar.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The Minimal Automorphism-Free Tree

A finite tree $T$ with $|V(T)| \geq 2$ is called {\it automorphism-free} if there is no non-trivial automorphism of $T$. Let $\mathcal{AFT}$ be the poset with the element set of all finite automorphism-free trees (up to graph isomorphism) ordered by $T_1 \preceq T_2$ if $T_1$ can be obtained from $T_2$ by successively deleting one leaf at a time in such a way that each intermediate tree is also automorphism-free. In this paper, we prove that $\mathcal{AFT}$ has a unique minimal element. This result gives an affirmative answer to the question asked by Rupinski.

0 citations0 reviewsNo code linkedOpen access