BEGIN:VCALENDAR VERSION:2.0 PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN CALSCALE:GREGORIAN METHOD:PUBLISH X-ORIGINAL-URL:https://dimag.ibs.re.kr X-WR-CALDESC:Events for Discrete Mathematics Group REFRESH-INTERVAL;VALUE=DURATION:PT1H X-Robots-Tag:noindex X-PUBLISHED-TTL:PT1H BEGIN:VTIMEZONE TZID:Asia/Seoul BEGIN:STANDARD TZOFFSETFROM:+0900 TZOFFSETTO:+0900 TZNAME:KST DTSTART:20170101T000000 END:STANDARD END:VTIMEZONE BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191121T163000 DTEND;TZID=Asia/Seoul:20191121T173000 DTSTAMP:20260420T111505 CREATED:20191028T154322Z LAST-MODIFIED:20240707T084339Z UID:1641-1574353800-1574357400@dimag.ibs.re.kr SUMMARY:Frédéric Meunier\, Topological bounds for graph representations over any field DESCRIPTION:Haviv (European Journal of Combinatorics\, 2019) has recently proved that some topological lower bounds on the chromatic number of graphs are also lower bounds on their orthogonality dimension over $\mathbb {R}$. We show that this holds actually for all known topological lower bounds and all fields. We also improve the topological bound he obtained for the minrank parameter over $\mathbb {R}$ – an important graph invariant from coding theory – and show that this bound is actually valid for all fields as well. The notion of independent representation over a matroid is introduced and used in a general theorem having these results as corollaries. Related complexity results are also discussed.\nThis is joint work with Meysam Alishahi. URL:https://dimag.ibs.re.kr/event/2019-11-21/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191119T163000 DTEND;TZID=Asia/Seoul:20191119T173000 DTSTAMP:20260420T111505 CREATED:20190924T042207Z LAST-MODIFIED:20240707T084346Z UID:1430-1574181000-1574184600@dimag.ibs.re.kr SUMMARY:Ruth Luo\, Induced Turán problems for hypergraphs DESCRIPTION:Let $F$ be a graph. We say that a hypergraph $\mathcal H$ is an induced Berge $F$ if there exists a bijective mapping $f$ from the edges of $F$ to the hyperedges of $\mathcal H$ such that for all $xy \in E(F)$\, $f(xy) \cap V(F) = \{x\,y\}$. In this talk\, we show asymptotics for the maximum number of edges in $r$-uniform hypergraphs with no induced Berge $F$. In particular\, this function is strongly related to the generalized Turán function $ex(n\,K_r\, F)$\, i.e.\, the maximum number of cliques of size $r$ in $n$-vertex\, $F$-free graphs.  Joint work with Zoltan Füredi. URL:https://dimag.ibs.re.kr/event/2019-11-19/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191112T163000 DTEND;TZID=Asia/Seoul:20191112T173000 DTSTAMP:20260420T111505 CREATED:20190920T115103Z LAST-MODIFIED:20240705T204218Z UID:1402-1573576200-1573579800@dimag.ibs.re.kr SUMMARY:Tony Huynh\, Stable sets in graphs with bounded odd cycle packing number DESCRIPTION:It is a classic result that the maximum weight stable set problem is efficiently solvable for bipartite graphs.  The recent bimodular algorithm of Artmann\, Weismantel and Zenklusen shows that it is also efficiently solvable for graphs without two disjoint odd cycles.  The complexity of the stable set problem for graphs without $k$ disjoint odd cycles is a long-standing open problem for all other values of $k$.  We prove that under the additional assumption that the input graph is embedded in a surface of bounded genus\, there is a polynomial-time algorithm for each fixed $k$.  Moreover\, we obtain polynomial-size extended formulations for the respective stable set polytopes. \nTo this end\, we show that 2-sided odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed surface. This result may be of independent interest and extends a theorem of Kawarabayashi and Nakamoto asserting that odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed orientable surface. \nEventually\, our findings allow us to reduce the original problem to the problem of finding a minimum-cost non-negative integer circulation of a certain homology class\, which we prove to be efficiently solvable in our case. \nThis is joint work with Michele Conforti\, Samuel Fiorini\, Gwenaël Joret\, and Stefan Weltge. URL:https://dimag.ibs.re.kr/event/2019-11-12/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191105T163000 DTEND;TZID=Asia/Seoul:20191105T173000 DTSTAMP:20260420T111505 CREATED:20191027T113022Z LAST-MODIFIED:20240707T085941Z UID:1636-1572971400-1572975000@dimag.ibs.re.kr SUMMARY:Sun Kim (김선)\, Two identities in Ramanujan’s Lost Notebook with Bessel function series DESCRIPTION:On page 335 in his lost notebook\, Ramanujan recorded without proofs two identities involving finite trigonometric sums and doubly infinite series of Bessel functions. We proved each of these identities under three different interpretations for the double series\, and showed that they are intimately connected with the classical circle and divisor problems in number theory. Furthermore\, we established many analogues and generalizations of them. This is joint work with Bruce C. Berndt and Alexandru Zaharescu. URL:https://dimag.ibs.re.kr/event/2019-11-05/ LOCATION:Room 1401\, Bldg. E6-1\, KAIST CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191029T163000 DTEND;TZID=Asia/Seoul:20191029T173000 DTSTAMP:20260420T111505 CREATED:20191027T110551Z LAST-MODIFIED:20240707T090010Z UID:1632-1572366600-1572370200@dimag.ibs.re.kr SUMMARY:Pascal Gollin\, A Cantor-Bernstein-type theorem for spanning trees in infinite graphs DESCRIPTION:Given a cardinal $\lambda$\, a $\lambda$-packing of a graph $G$ is a family of $\lambda$ many edge-disjoint spanning trees of $G$\, and a $\lambda$-covering of $G$ is a family of spanning trees covering $E(G)$. \nWe show that if a graph admits a $\lambda$-packing and a $\lambda$-covering  then the graph also admits a decomposition into $\lambda$ many spanning trees. In this talk\, we concentrate on the case of $\lambda$ being an infinite cardinal. Moreover\, we will provide a new and simple proof for a theorem of Laviolette characterising the existence of a $\lambda$-packing\, as well as for a theorem of Erdős and Hajnal characterising the existence of a $\lambda$-covering. \nJoint work with Joshua Erde\, Attila Joó\, Paul Knappe and Max Pitz. URL:https://dimag.ibs.re.kr/event/2019-10-29/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191022T163000 DTEND;TZID=Asia/Seoul:20191022T173000 DTSTAMP:20260420T111505 CREATED:20190920T222518Z LAST-MODIFIED:20240707T090027Z UID:1407-1571761800-1571765400@dimag.ibs.re.kr SUMMARY:Joonkyung Lee (이준경)\, On some properties of graph norms DESCRIPTION:For a graph $H$\, its homomorphism density in graphs naturally extends to the space of two-variable symmetric functions $W$ in $L^p$\, $p\geq e(H)$\, denoted by $t_H(W)$. One may then define corresponding functionals $\|W\|_{H}:=|t_H(W)|^{1/e(H)}$ and $\|W\|_{r(H)}:=t_H(|W|)^{1/e(H)}$ and say that $H$ is (semi-)norming if $\|.\|_{H}$ is a (semi-)norm and that $H$ is weakly norming if $\|.\|_{r(H)}$ is a norm. \nWe obtain some results that contribute to the theory of (weakly) norming graphs. Firstly\, we show that ‘twisted’ blow-ups of cycles\, which include $K_{5\,5}\setminus C_{10}$ and $C_6\square K_2$\, are not weakly norming. This answers two questions of Hatami\, who asked whether the two graphs are weakly norming. Secondly\, we prove that $\|.\|_{r(H)}$ is not uniformly convex nor uniformly smooth\, provided that $H$ is weakly norming. This answers another question of Hatami\, who estimated the modulus of convexity and smoothness of $\|.\|_{H}$. We also prove that every graph $H$ without isolated vertices is (weakly) norming if and only if each component is an isomorphic copy of a (weakly) norming graph. This strong factorisation result allows us to assume connectivity of $H$ when studying graph norms. Based on joint work with Frederik Garbe\, Jan Hladký\, and Bjarne Schülke. URL:https://dimag.ibs.re.kr/event/2019-10-22/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191015T163000 DTEND;TZID=Asia/Seoul:20191015T173000 DTSTAMP:20260420T111505 CREATED:20190920T222934Z LAST-MODIFIED:20240707T090036Z UID:1409-1571157000-1571160600@dimag.ibs.re.kr SUMMARY:Zi-Xia Song (宋梓霞)\, Ramsey numbers of cycles under Gallai colorings DESCRIPTION:For a graph $H$ and an integer $k\ge1$\, the $k$-color Ramsey number $R_k(H)$ is the least integer $N$ such that every $k$-coloring of the edges of the complete graph $K_N$ contains a monochromatic copy of $H$. Let $C_m$ denote the cycle on $m\ge4 $ vertices. For odd cycles\, Bondy and Erd\H{o}s in 1973 conjectured that for all $k\ge1$ and $n\ge2$\, $R_k(C_{2n+1})=n\cdot 2^k+1$. Recently\, this conjecture has been verified to be true for all fixed $k$ and all $n$ sufficiently large by Jenssen and Skokan; and false for all fixed $n$ and all $k$ sufficiently large by Day and Johnson. Even cycles behave rather differently in this context. Little is known about the behavior of $R_k(C_{2n})$ in general. In this talk we will present our recent results on Ramsey numbers of cycles under Gallai colorings\, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles. We prove that the aforementioned conjecture holds for all $k$ and all $n$ under Gallai colorings. We also completely determine the Ramsey number of even cycles under Gallai colorings. \nJoint work with Dylan Bruce\, Christian Bosse\, Yaojun Chen and Fangfang Zhang. URL:https://dimag.ibs.re.kr/event/2019-10-15/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191010T163000 DTEND;TZID=Asia/Seoul:20191010T173000 DTSTAMP:20260420T111505 CREATED:20190710T015315Z LAST-MODIFIED:20240707T090044Z UID:1081-1570725000-1570728600@dimag.ibs.re.kr SUMMARY:Alexandr V. Kostochka\, Reconstructing graphs from smaller subgraphs DESCRIPTION:A graph or graph property is $\ell$-reconstructible if it is determined by the multiset of all subgraphs obtained by deleting $\ell$ vertices. Apart from the famous Graph Reconstruction Conjecture\, Kelly conjectured in 1957 that for each $\ell\in\mathbb N$\, there is an integer $n=n(\ell)$ such that every graph with at least $n$ vertices is $\ell$-reconstructible. \nWe show that for each $n\ge7$ and every $n$-vertex graph $G$\, the degree list and connectedness of $G$ are $3$-reconstructible\, and the threshold $n\geq 7$ is sharp for both properties.‌ We also show that all $3$-regular graphs are $2$-reconstructible. URL:https://dimag.ibs.re.kr/event/2019-10-10/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191008T163000 DTEND;TZID=Asia/Seoul:20191008T173000 DTSTAMP:20260420T111505 CREATED:20190709T235022Z LAST-MODIFIED:20240705T210004Z UID:1072-1570552200-1570555800@dimag.ibs.re.kr SUMMARY:Alexandr V. Kostochka\, On Ramsey-type problems for paths and cycles in dense graphs DESCRIPTION:A well-known Ramsey-type puzzle for children is to prove that among any 6 people either there are 3 who know each other or there are 3 who do not know each other. More generally\, a graph $G$ arrows a graph $H$ if for any coloring of the edges of $G$ with two colors\, there is a monochromatic copy of $H$. In these terms\, the above puzzle claims that the complete $6$-vertex graph $K_6$ arrows the complete $3$-vertex graph $K_3$. \nWe consider sufficient conditions on the dense host graphs $G$ to arrow long paths and even cycles. In particular\, for large $n$ we describe all multipartite graphs that arrow paths and cycles with $2n$ edges. This implies a conjecture by Gyárfás\, Ruszinkó\, Sárkőzy and Szemerédi from 2007 for such $n$. Also for large $n$ we find which minimum degree in a $(3n-1)$-vertex graph $G$ guarantees that $G$ arrows the $2n$-vertex path. This yields a more recent conjecture of Schelp. \nThis is joint work with Jozsef Balogh\, Mikhail Lavrov and Xujun Liu. URL:https://dimag.ibs.re.kr/event/2019-10-08/ LOCATION:Room 1501\, Bldg. E6-1\, KAIST CATEGORIES:Colloquium END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20191001T163000 DTEND;TZID=Asia/Seoul:20191001T173000 DTSTAMP:20260420T111505 CREATED:20190916T044737Z LAST-MODIFIED:20240705T204218Z UID:1387-1569947400-1569951000@dimag.ibs.re.kr SUMMARY:Casey Tompkins\, Extremal problems for Berge hypergraphs DESCRIPTION:Given a graph $G$\, there are several natural hypergraph families one can define. Among the least restrictive is the family $BG$ of so-called Berge copies of the graph $G$. In this talk\, we discuss Turán problems for families $BG$ in $r$-uniform hypergraphs for various graphs $G$. In particular\, we are interested in general results in two settings: the case when $r$ is large and $G$ is any graph where this Turán number is shown to be eventually subquadratic\, as well as the case when $G$ is a tree where several exact results can be obtained. The results in the first part are joint with Grósz and Methuku\, and the second part with Győri\, Salia and Zamora. URL:https://dimag.ibs.re.kr/event/2019-10-01/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20190919T163000 DTEND;TZID=Asia/Seoul:20190919T173000 DTSTAMP:20260420T111505 CREATED:20190815T090406Z LAST-MODIFIED:20240707T090104Z UID:1277-1568910600-1568914200@dimag.ibs.re.kr SUMMARY:Cory Palmer\, A survey of Turán-type subgraph counting problems DESCRIPTION:Let $F$ and $H$ be graphs. The subgraph counting function $\operatorname{ex}(n\,H\,F)$ is defined as the maximum possible number of subgraphs $H$ in an $n$-vertex $F$-free graph. This function is a direct generalization of the Turán function as $\operatorname{ex}(n\,F)=\operatorname{ex}(n\,K_2\,F)$. The systematic study of $\operatorname{ex}(n\,H\,F)$ was initiated by Alon and Shikhelman in 2016 who generalized several classical results in extremal graph theory to the subgraph counting setting. Prior to their paper\, a number of individual cases were investigated; a well-known example is the question to determine the maximum number of pentagons in a triangle-free graph. In this talk we will survey results on the function $\operatorname{ex}(n\,H\,F)$ including a number of recent papers. We will also discuss this function’s connection to hypergraph Turán problems. URL:https://dimag.ibs.re.kr/event/2019-09-19/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20190910T163000 DTEND;TZID=Asia/Seoul:20190910T173000 DTSTAMP:20260420T111505 CREATED:20190903T042102Z LAST-MODIFIED:20240707T090111Z UID:1337-1568133000-1568136600@dimag.ibs.re.kr SUMMARY:Kevin Hendrey\, The minimum connectivity forcing forest minors in large graphs DESCRIPTION:Given a graph $G$\, we define $\textrm{ex}_c(G)$ to be the minimum value of $t$ for which there exists a constant $N(t\,G)$ such that every $t$-connected graph with at least $N(t\,G)$ vertices contains $G$ as a minor. The value of $\textrm{ex}_c(G)$ is known to be tied to the vertex cover number $\tau(G)$\, and in fact $\tau(G)\leq \textrm{ex}_c(G)\leq \frac{31}{2}(\tau(G)+1)$. We give the precise value of $\textrm{ex}_c(G)$ when $G$ is a forest. In particular we find that $\textrm{ex}_c(G)\leq \tau(G)+2$ in this setting\, which is tight for infinitely many forests. URL:https://dimag.ibs.re.kr/event/2019-09-10/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20190820T163000 DTEND;TZID=Asia/Seoul:20190820T173000 DTSTAMP:20260420T111505 CREATED:20190619T105835Z LAST-MODIFIED:20240707T090132Z UID:1031-1566318600-1566322200@dimag.ibs.re.kr SUMMARY:Mihyun Kang (강미현)\, The genus of a random graph and the fragile genus property DESCRIPTION:In this talk we shall discuss how quickly the genus of the Erdős-Rényi random graph grows as the number of edges increases and how dramatically a small number of random edges can increase the genus of a randomly perturbed graph. (Joint work with Chris Dowden and Michael Krivelevich) URL:https://dimag.ibs.re.kr/event/2019-08-20/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20190716T163000 DTEND;TZID=Asia/Seoul:20190716T173000 DTSTAMP:20260420T111505 CREATED:20190627T074550Z LAST-MODIFIED:20240707T090234Z UID:1060-1563294600-1563298200@dimag.ibs.re.kr SUMMARY:Dabeen Lee (이다빈)\, Integrality of set covering polyhedra and clutter minors DESCRIPTION:Given a finite set of elements $V$ and a family $\mathcal{C}$ of subsets of $V$\, the set covering problem is to find a minimum cardinality subset of $V$ intersecting every subset in the family $\mathcal{C}$. The set covering problem\, also known as the hitting set problem\, admits a simple integer linear programming formulation. The constraint system of the integer linear programming formulation defines a polyhedron\, and we call it the set covering polyhedron of $\mathcal{C}$. We say that a set covering polyhedron is integral if every extreme point is an integer lattice point. Although the set covering problem is NP-hard in general\, conditions under which the problem becomes polynomially solvable have been studied. If the set covering polyhedron is integral\, then it is straightforward that the problem can be solved using a polynomial-time algorithm for linear programming. \nIn this talk\, we will focus on the question of when the set covering polyhedron is integral. We say that the family $\mathcal{C}$ is a clutter if every subset in $\mathcal{C}$ is inclusion-wise minimal. As taking out non-minimal subsets preserves integrality\, we may assume that $\mathcal{C}$ is a clutter. We call $\mathcal{C}$ ideal if the set covering polyhedron of it is integral. To understand when a clutter is ideal\, the notion of clutter minors is important in that $\mathcal{C}$ is ideal if and only if so is every minor of it. We will study two fundamental classes of non-ideal clutters\, namely\, deltas and the blockers of extended odd holes. We will characterize when a clutter contains either a delta or the blocker of an extended odd hole as a minor. \nThis talk is based on joint works with Ahmad Abdi and Gérard Cornuéjols. URL:https://dimag.ibs.re.kr/event/2019-07-16/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20190625T163000 DTEND;TZID=Asia/Seoul:20190625T173000 DTSTAMP:20260420T111505 CREATED:20190520T133325Z LAST-MODIFIED:20240707T090302Z UID:913-1561480200-1561483800@dimag.ibs.re.kr SUMMARY:Patrice Ossona de Mendez\, A model theoretical approach to sparsity DESCRIPTION:We discuss how the model theoretic notion of first-order transduction allows to define a notion of structural sparsity\, and give some example of applications\, like existence of low shrub-depth decompositions for tranductions of bounded expansion classes\, characterization of transductions of classes with bounded pathwidth\, decompositions of graphs with bounded rank-width into cographs. URL:https://dimag.ibs.re.kr/event/2019-06-25/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20190619T163000 DTEND;TZID=Asia/Seoul:20190619T173000 DTSTAMP:20260420T111505 CREATED:20190418T080534Z LAST-MODIFIED:20240707T090333Z UID:789-1560961800-1560965400@dimag.ibs.re.kr SUMMARY:Suil O (오수일)\, An odd [1\,b]-factor in regular graphs from eigenvalues DESCRIPTION:An odd $[1\,b]$-factor of a graph is a spanning subgraph $H$ such that for every vertex $v \in V(G)$\, $1 \le d_H(v) \le b$\, and $d_H(v)$ is odd. For positive integers $r \ge 3$ and $b \le r$\, Lu\, Wu\, and Yang gave an upper bound for the third largest eigenvalue in an $r$-regular graph with even number of vertices to guarantee the existence of an odd [1\,b]-factor.\nIn this talk\, we improve their bound. URL:https://dimag.ibs.re.kr/event/2019-06-19/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20190603T163000 DTEND;TZID=Asia/Seoul:20190603T173000 DTSTAMP:20260420T111505 CREATED:20190411T160640Z LAST-MODIFIED:20240707T090357Z UID:770-1559579400-1559583000@dimag.ibs.re.kr SUMMARY:Jinyoung Park (박진영)\, The number of maximal independent sets in the Hamming cube DESCRIPTION:Let $Q_n$ be the $n$-dimensional Hamming cube (hypercube) and $N=2^n$. We prove that the number of maximal independent sets in $Q_n$ is asymptotically $2n2^{N/4}$\, as was conjectured by Ilinca and Kahn in connection with a question of Duffus\, Frankl and Rödl. The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof of the upper bound draws on various tools\, among them “stability” results for maximal independent set counts and old and new results on isoperimetric behavior in $Q_n$. This is joint work with Jeff Kahn. URL:https://dimag.ibs.re.kr/event/2019-06-03/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20190520T163000 DTEND;TZID=Asia/Seoul:20190520T173000 DTSTAMP:20260420T111505 CREATED:20190304T123855Z LAST-MODIFIED:20240707T090406Z UID:642-1558369800-1558373400@dimag.ibs.re.kr SUMMARY:Lars Jaffke\, A complexity dichotomy for critical values of the b-chromatic number of graphs DESCRIPTION:A $b$-coloring of a graph $G$ is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The $b$-Coloring problem asks whether a graph $G$ has a $b$-coloring with $k$ colors.\nThe $b$-chromatic number of a graph $G$\, denoted by $\chi_b(G)$\, is the maximum number $k$ such that $G$ admits a $b$-coloring with $k$ colors. We consider the complexity of the $b$-Coloring problem\, whenever the value of $k$ is close to one of two upper bounds on $\chi_b(G)$: The maximum degree $\Delta(G)$ plus one\, and the $m$-degree\, denoted by $m(G)$\, which is defined as the maximum number $i$ such that $G$ has $i$ vertices of degree at least $i-1$. We obtain a dichotomy result stating that for fixed $k \in\{\Delta(G) + 1 − p\, m(G) − p\}$\, the problem is polynomial-time solvable whenever $p\in\{0\, 1\}$ and\, even when $k = 3$\, it is NP-complete whenever $p \ge 2$.\nWe furthermore consider parameterizations of the $b$-Coloring problem that involve the maximum degree $\Delta(G)$ of the input graph $G$ and give two FPT-algorithms. First\, we show that deciding whether a graph G has a $b$-coloring with $m(G)$ colors is FPT parameterized by $\Delta(G)$. Second\, we show that $b$-Coloring is FPT parameterized by $\Delta(G) + \ell_k(G)$\, where $\ell_k(G)$ denotes the number of vertices of degree at least $k$.\nThis is joint work with Paloma T. Lima. URL:https://dimag.ibs.re.kr/event/2019-05-20/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20190516T163000 DTEND;TZID=Asia/Seoul:20190516T173000 DTSTAMP:20260420T111505 CREATED:20190118T041528Z LAST-MODIFIED:20240707T090507Z UID:423-1558024200-1558027800@dimag.ibs.re.kr SUMMARY:Xin Zhang (张欣)\, On equitable tree-colorings of graphs DESCRIPTION:An equitable tree-$k$-coloring of a graph is a vertex coloring using $k$ distinct colors such that every color class (i.e\, the set of vertices in a common color) induces a forest and the sizes of any two color classes differ by at most one. The minimum integer $k$ such that a graph $G$ is equitably tree-$k$-colorable is the equitable vertex arboricity of $G$\, denoted by $va_{eq}(G)$. A graph that is equitably tree-$k$-colorable may admits no equitable tree-$k’$-coloring for some $k’>k$. For example\, the complete bipartite graph $K_{9\,9}$ has an equitable tree-$2$-coloring but is not equitably tree-3-colorable. In view of this a new chromatic parameter so-called the equitable vertex arborable threshold is introduced. Precisely\, it is the minimum integer $k$ such that $G$ has an equitable tree-$k’$-coloring for any integer $k’\geq k$\, and is denoted by $va_{eq}^*(G)$. The concepts of the equitable vertex arboricity and the equitable vertex arborable threshold were introduced by J.-L. Wu\, X. Zhang and H. Li in 2013. In 2016\, X. Zhang also introduced the list analogue of the equitable tree-$k$-coloring. There are many interesting conjectures on the equitable (list) tree-colorings\, one of which\, for example\, conjectures that every graph with maximum degree at most $\Delta$ is equitably tree-$k$-colorable for any integer $k\geq (\Delta+1)/2$\, i.e\, $va_{eq}^*(G)\leq \lceil(\Delta+1)/2\rceil$. In this talk\, I review the recent progresses on the studies of the equitable tree-colorings from theoretical results to practical algorithms\, and also share some interesting problems for further research. URL:https://dimag.ibs.re.kr/event/2019-05-16/ LOCATION:Room B232\, IBS (기초과학연구원) CATEGORIES:Discrete Math Seminar END:VEVENT BEGIN:VEVENT DTSTART;TZID=Asia/Seoul:20190508T163000 DTEND;TZID=Asia/Seoul:20190508T173000 DTSTAMP:20260420T111505 CREATED:20190310T074230Z LAST-MODIFIED:20240707T090513Z UID:673-1557333000-1557336600@dimag.ibs.re.kr SUMMARY:Sang June Lee (이상준)\, On strong Sidon sets of integers DESCRIPTION:Let $\mathbb N$ be the set of natural numbers. A set $A\subset \mathbb N$ is called a Sidon set if the sums $a_1+a_2$\, with $a_1\,a_2\in S$ and $a_1\leq a_2$\, are distinct\, or equivalently\, if \[|(x+w)-(y+z)|\geq 1\] for every $x\,y\,z\,w\in S$ with $x