김석진

Archive of posts with tag '김석진'

  • Seog-Jin Kim (김석진), Signed coloring and list coloring of k-chromatic graphs

    IBS/KAIST Joint Discrete Math Seminar

    Signed colouring and list colouring of k-chromatic graphs
    Seog-Jin Kim (김석진)
    Department of Mathematics Education, Konkuk University, Seoul
    2019/1/28 Mon 4PM-5PM (Room B232, IBS)
    A signed graph is a pair (G, σ), where G is a graph and σ: E(G) → {1,-1} is a signature of G. A set S of integers is symmetric if I∈S implies that -i∈S. A k-colouring of (G,σ) is a mapping f:V(G) → Nk such that for each edge e=uv, f(x)≠σ(e) f(y), where Nk is a symmetric integer set of size k. We define the signed chromatic number of a graph G to be the minimum integer k such that for any signature σ of G, (G, σ) has a k-colouring. Let f(n,k) be the maximum signed chromatic number of an n-vertex k-chromatic graph. This paper determines the value of f(n,k) for all positive integers n ≥ k. Then we study list colouring of signed graphs. A list assignment L of G is called symmetric if L(v) is a symmetric integer set for each vertex v. The weak signed choice number ch±w(G) of a graph G is defined to be the minimum integer k such that for any symmetric k-list assignment L of G, for any signature σ on G, there is a proper L-colouring of (G, σ). We prove that the difference ch±w(G)-χ±(G) can be arbitrarily large. On the other hand, ch±w(G) is bounded from above by twice the list vertex arboricity of G. Using this result, we prove that ch±w(K2⋆n)= χ±(K2⋆n) = ⌈2n/3⌉ + ⌊2n/3⌋. This is joint work with Ringi Kim and Xuding Zhu.

    Tags:

  • 1st Korean Workshop on Graph Theory
    1st Korean Workshop on Graph Theory
    August 26-28, 2015
    KAIST  (E6-1 1501 & 3435)
    • Program Book
    • Currently, we are planning to have talks in KOREAN.
    • Students/postdocs may get the support for the accommodation. (Hotel Interciti)
    • Others may contact us if you wish to book a hotel at a pre-negotiated price. Please see the website.
    • We may or may not have contributed talks. If you want, please contact us.
    • PLEASE REGISTER UNTIL AUGUST 16.
    Location: KAIST
    • Room 1501 of E6-1 (August 26, 27)
    • Room 3435 of E6-1 (August 28)
    Invited Speakers:
    Organizers:
    Tags:

  • Seog-Jin Kim, Bipartite graphs whose squares are not chromatic-choosable
    Bipartite graphs whose squares are not chromatic-choosable
    Seog-Jin Kim
    Konkuk University
    2014/09/19 *Friday* 4PM-5PM
    Room 3433
    The square G^2 of a graph G is the graph defined on V(G) such that two vertices u and v are adjacent in G^2 if the distance between u and v in G is at most 2. Let \chi(H) and \chi_{\ell}(H) be the chromatic number and the list chromatic number of H, respectively. A graph H is called {chromatic-choosable} if \chi_{\ell} (H) = \chi(H). It is an interesting problem to find graphs that are chromatic-choosable.</p>

    Motivated by the List Total Coloring Conjecture, Kostochka and Woodall (2001) proposed the List Square Coloring Conjecture which states that G^2 is chromatic-choosable for every graph G. Recently, Kim and Park showed that the List Square Coloring Conjecture does not hold in general by finding a family of graphs whose squares are complete multipartite graphs with partite sets of unbounded size. It is a well-known fact that the List Total Coloring Conjecture is true if the List Square Coloring Conjecture holds for special class of bipartite graphs. On the other hand, the counterexamples to the List Square Coloring Conjecture are not bipartite graphs. Hence a natural question is whether G^2 is chromatic-choosable or not for every bipartite graph G.

    In this paper, we give a bipartite graph G such that \chi_{\ell} (G^2) \neq \chi(G^2). Moreover, we show that the value \chi_{\ell}(G^2) - \chi(G^2) can be arbitrarily large. This is joint work with Boram Park.

    Tags:

  • Seog-jin Kim (김석진), On-line list colouring of complete multipartite graphs
    On-line list colouring of complete multipartite graphs
    Seog-Jin Kim (김석진)
    Dept. of Mathematics Education, Konkuk University, Seoul, Korea.
    2011/4/18 Wed 4PM-5PM</em>
    The well-known Ohba Conjecture says that every graph G with |V(G)|≤ 2χ(G)+1 is chromatic choosable.
    This paper studies an on-line version of Ohba Conjecture. We prove that unlike the off-line case, for k≥3, the complete multipartite graph K2*(k-1), 3 is not on-line chromatic-choosable. Based on this result, the on-line version of Ohba Conjecture is modified as follows: Every graph G with |V(G)|≥ 2χ(G) is on-line chromatic choosable. We present an explicit strategy to show that for any positive integer k, the graph K2*k is on-line chromatic-choosable. We then present a minimal function g for which the graph K2*(k-1), 3 is on-line g-choosable. This is joint work with Young Soo Kwon, Daphne Der-Fen Liu, and Xuding Zhu.
    Tags:

  • Seog-Jin Kim (김석진), Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree
    Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree
    Seog-Jin Kim (김석진)
    Dept. of Mathematics Education, Konkuk University, Seoul, Korea.
    2011/3/10 Thu 5PM-6PM
    Say that a graph with maximum degree at most d is d-bounded. For d>k, we prove a sharp sparseness condition for decomposability into k forests and a d-bounded graph. Consequences ar e that every graph with fractional arboricity at most k+ d/(k+d+1) has such a decomposition, and (for k=1) every graph with maximum average degree less than 2+2d/(d+2) decomposes into a forest and a d-bounded graph. When d=k+1, and when k=1 and d≤6, the d-bounded graph in the decomposition can also be required to be a forest. When k=1 and d≤2, the d-bounded forest can also be required to have at most d edges in each component.
    This is joint work with A.V. Kostochka, D.B. West, H. Wu, and X. Zhu.
    Tags:

  • Seog-Jin Kim (김석진), Injective colorings of graphs with low average degree
    Injective colorings of graphs with low average degree
    Seog-Jin Kim (김석진)
    Dept. of Mathematics Education, Konkuk University, Seoul, Korea.
    2009/02/27 Fri, 4PM-5PM 3PM-4PM
    An injective coloring of a graph G is an assignment of colors to the vertices of G so that any two vertices with a common neighbors receives distinct colors. The injective chromatic number, \chi_i(G), is the minimum number of colors needed for an injective coloring. Let mad(G) be the maximum average degree of G. In this paper, we show that \chi_i(G)\leq\Delta + 2 if \Delta(G) \geq 4 and mad(G) \leq \frac{14}{5}. When \Delta(G) = 3, we show that mad(G) < \frac{36}{13}[/latex] implies [latex]\chi_i(G) \leq 5[/latex]. This is sharp; there is a subcubic graph [latex]H[/latex] such that [latex]mad(H) = \frac{36}{13}[/latex], but [latex]\chi_i(H) = 6[/latex]. This is joint work with Daniel Cranston and Gexin Yu.
    Tags:

  • Seog-Jin Kim (김석진), List-coloring the Square of a Subcubic Graph
    List-coloring the Square of a Subcubic Graph
    Seog-Jin Kim (김석진)
    Dept. of Mathematics Education, Konkuk University, Seoul, Korea.
    2008/05/01 Thu, 3PM-4PM

    The square G2 of a graph G is the graph with the same vertex set as G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that for a planar graph G with maximum degree Δ(G)=3 we have χ(G2)≤7. Kostochka and Woodall conjectured that for every graph, the list-chromatic number of G2 equals the chromatic number of G2, that is χl(G2)=χ(G2) for all G. If true, this conjecture (together with Thomassen’s result) implies that every planar graph G with Δ(G)=3 satisfies χl(G2)≤7. We prove that every graph (not necessarily planar) with Δ(G)=3 other than the Petersen graph satisfies χl(G2)≤8 (and this is best possible). In addition, we show that if G is a planar graph with Δ(G)=3 and girth g(G)≥7, then χl(G2)≤7. Dvořák, Škrekovski, and Tancer showed that if G is a planar graph with Δ(G)=3 and girth g(G)≥10, then χl(G2)≤6. We improve the girth bound to show that: if G is a planar graph with Δ(G)=3 and g(G)≥9, then χl(G2)≤6. This is joint work with Daniel Cranston.</div>

    Tags:

Monthly Archives