Dvořák, Zdeněk; Kawarabayashi, Ken-ichi Additive non-approximability of chromatic number in proper minor-closed classes. (English) Zbl 1503.05102 J. Comb. Theory, Ser. B 158, Part 1, 74-92 (2023). MSC: 05C75 05C15 05C85 68Q25 68W25 PDFBibTeX XMLCite \textit{Z. Dvořák} and \textit{K.-i. Kawarabayashi}, J. Comb. Theory, Ser. B 158, Part 1, 74--92 (2023; Zbl 1503.05102) Full Text: DOI
Gorsky, Maximilian; Kawarabayashi, Ken-ichi; Kreutzer, Stephan; Wiederrecht, Sebastian Packing even directed circuits quarter-integrally. arXiv:2311.16816 Preprint, arXiv:2311.16816 [math.CO] (2023). MSC: 05C20 05C38 05C83 05C85 68R10 BibTeX Cite \textit{M. Gorsky} et al., ``Packing even directed circuits quarter-integrally'', Preprint, arXiv:2311.16816 [math.CO] (2023) Full Text: arXiv OA License
Kawarabayashi, Ken-ichi; Klavík, Pavel; Mohar, Bojan; Nedela, Roman; Zeman, Peter Isomorphisms of maps on the sphere. (English) Zbl 1468.05187 Cunningham, Gabriel (ed.) et al., Polytopes and discrete geometry. AMS special session, Northeastern University, Boston, MA, USA, April 21–22, 2018. Providence, RI: American Mathematical Society (AMS). Contemp. Math. 764, 125-147 (2021). MSC: 05C60 05C85 05C10 52B10 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} et al., Contemp. Math. 764, 125--147 (2021; Zbl 1468.05187) Full Text: DOI
Kawarabayashi, Ken-ichi; Xu, Chao Minimum violation vertex maps and their applications to cut problems. (English) Zbl 1453.05072 SIAM J. Discrete Math. 34, No. 4, 2183-2207 (2020). MSC: 05C60 05C75 05C85 05C20 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} and \textit{C. Xu}, SIAM J. Discrete Math. 34, No. 4, 2183--2207 (2020; Zbl 1453.05072) Full Text: DOI
Eickmeyer, Kord; van den Heuvel, Jan; Kawarabayashi, Ken-Ichi; Kreutzer, Stephan; Ossona De Mendez, Patrice; Pilipczuk, Michał; Quiroz, Daniel A.; Rabinovich, Roman; Siebertz, Sebastian Model-checking on ordered structures. (English) Zbl 1446.68092 ACM Trans. Comput. Log. 21, No. 2, Article No. 11, 28 p. (2020). MSC: 68Q60 03B70 05C75 05C83 68Q25 PDFBibTeX XMLCite \textit{K. Eickmeyer} et al., ACM Trans. Comput. Log. 21, No. 2, Article No. 11, 28 p. (2020; Zbl 1446.68092) Full Text: DOI arXiv
Kawarabayashi, Ken-ichi; Sidiropoulos, Anastasios Polylogarithmic approximation for Euler genus on bounded degree graphs. (English) Zbl 1433.68299 Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 164-175 (2019). MSC: 68R10 05C10 05C85 68W25 68W40 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} and \textit{A. Sidiropoulos}, in: Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC '19, Phoenix, AZ, USA, June 23--26, 2019. New York, NY: Association for Computing Machinery (ACM). 164--175 (2019; Zbl 1433.68299) Full Text: DOI
Dvorák, Zdenek; Kawarabayashi, Ken-Ichi Additive non-approximability of chromatic number in proper minor-closed classes. (English) Zbl 1499.68267 Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 47, 12 p. (2018). MSC: 68R10 05C15 05C83 68Q17 68W25 PDFBibTeX XMLCite \textit{Z. Dvorák} and \textit{K.-I. Kawarabayashi}, LIPIcs -- Leibniz Int. Proc. Inform. 107, Article 47, 12 p. (2018; Zbl 1499.68267) Full Text: DOI arXiv
Kawarabayashi, Ken-ichi; Kobayashi, Yusuke All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs. (English) Zbl 1392.05050 SIAM J. Comput. 47, No. 4, 1483-1504 (2018). MSC: 05C21 05C10 05C85 68W25 90C27 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} and \textit{Y. Kobayashi}, SIAM J. Comput. 47, No. 4, 1483--1504 (2018; Zbl 1392.05050) Full Text: DOI
Kawarabayashi, Ken-Ichi; Thorup, Mikkel Coloring 3-colorable graphs with less than \(n^{1/5}\) colors. (English) Zbl 1426.05166 J. ACM 64, No. 1, Article No. 4, 23 p. (2017). MSC: 05C85 05C15 68Q25 90C22 PDFBibTeX XMLCite \textit{K.-I. Kawarabayashi} and \textit{M. Thorup}, J. ACM 64, No. 1, Article No. 4, 23 p. (2017; Zbl 1426.05166) Full Text: DOI
Fukunaga, Takuro (ed.); Kawarabayashi, Ken-ichi (ed.) Combinatorial optimization and graph algorithms. Communications of NII Shonan meetings. (English) Zbl 1394.90011 Singapore: Springer (ISBN 978-981-10-6146-2/hbk; 978-981-10-6147-9/ebook). ix, 120 p. (2017). MSC: 90-06 90C27 90C35 05-06 05C85 00B25 PDFBibTeX XMLCite \textit{T. Fukunaga} (ed.) and \textit{K.-i. Kawarabayashi} (ed.), Combinatorial optimization and graph algorithms. Communications of NII Shonan meetings. Singapore: Springer (2017; Zbl 1394.90011) Full Text: DOI
Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs. (English) Zbl 1374.05137 Combinatorica 35, No. 4, 477-495 (2015). MSC: 05C38 05C83 05C85 05C45 05C40 PDFBibTeX XMLCite \textit{K.-I. Kawarabayashi} and \textit{Y. Kobayashi}, Combinatorica 35, No. 4, 477--495 (2015; Zbl 1374.05137) Full Text: DOI
Kawarabayashi, Ken-ichi; Sidiropoulos, Anastasios Beyond the Euler characteristic: approximating the genus of general graphs (extended abstract). (English) Zbl 1321.05063 Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 675-682 (2015). MSC: 05C10 68W25 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} and \textit{A. Sidiropoulos}, in: Proceedings of the 47th annual ACM symposium on theory of computing, STOC '15, Portland, OR, USA, June 14--17, 2015. New York, NY: Association for Computing Machinery (ACM). 675--682 (2015; Zbl 1321.05063) Full Text: DOI arXiv
Kawarabayashi, Ken-ichi; Thorup, Mikkel Deterministic global minimum cut of a simple graph in near-linear time. (English) Zbl 1321.05268 Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 665-674 (2015). MSC: 05C85 05C40 05C70 68Q25 68R10 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} and \textit{M. Thorup}, in: Proceedings of the 47th annual ACM symposium on theory of computing, STOC '15, Portland, OR, USA, June 14--17, 2015. New York, NY: Association for Computing Machinery (ACM). 665--674 (2015; Zbl 1321.05268) Full Text: DOI
Kawarabayashi, Ken-ichi; Thorup, Mikkel Coloring 3-colorable graphs with \(o(n^{1/5})\) colors. (English) Zbl 1359.05123 Mayr, Ernst W. (ed.) et al., 31st international symposium on theoretical aspects of computer science, STACS’ 14, Lyon, France, March 5–8, 2014. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-65-1). LIPIcs – Leibniz International Proceedings in Informatics 25, 458-469 (2014). MSC: 05C85 05C15 68W25 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} and \textit{M. Thorup}, LIPIcs -- Leibniz Int. Proc. Inform. 25, 458--469 (2014; Zbl 1359.05123) Full Text: DOI
Elberfeld, Michael; Kawarabayashi, Ken-ichi Embedding and canonizing graphs of bounded genus in logspace. (English) Zbl 1315.68254 Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 383-392 (2014). MSC: 68U05 05C10 05C51 68Q25 PDFBibTeX XMLCite \textit{M. Elberfeld} and \textit{K.-i. Kawarabayashi}, in: Proceedings of the 46th annual ACM symposium on theory of computing, STOC '14, New York, NY, USA, May 31 -- June 3, 2014. New York, NY: Association for Computing Machinery (ACM). 383--392 (2014; Zbl 1315.68254) Full Text: DOI
Kawarabayashi, Ken-ichi; Kobayashi, Yusuke; Kreutzer, Stephan An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem. (English) Zbl 1315.05132 Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 70-78 (2014). MSC: 05C83 05C20 05C38 68Q25 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} et al., in: Proceedings of the 46th annual ACM symposium on theory of computing, STOC '14, New York, NY, USA, May 31 -- June 3, 2014. New York, NY: Association for Computing Machinery (ACM). 70--78 (2014; Zbl 1315.05132) Full Text: DOI
Kawarabayashi, Ken-ichi Totally odd subdivisions and parity subdivisions: structures and coloring. (English) Zbl 1423.05175 Khanna, Sanjeev (ed.), Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, January 6–8, 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1013-1029 (2013). MSC: 05C85 05C15 05C75 68W25 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi}, in: Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, January 6--8, 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1013--1029 (2013; Zbl 1423.05175) Full Text: DOI Link
Dvořák, Zdeněk; Kawarabayashi, Ken-ichi List-coloring embedded graphs. (English) Zbl 1423.05063 Khanna, Sanjeev (ed.), Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, January 6–8, 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1004-1012 (2013). MSC: 05C15 05C10 05C85 68W40 PDFBibTeX XMLCite \textit{Z. Dvořák} and \textit{K.-i. Kawarabayashi}, in: Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, January 6--8, 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1004--1012 (2013; Zbl 1423.05063) Full Text: DOI arXiv
Kawarabayashi, Ken-ichi 5-coloring \(K_{3,k}\)-minor-free graphs. (English) Zbl 1423.05174 Khanna, Sanjeev (ed.), Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, January 6–8, 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 985-1003 (2013). MSC: 05C85 05C15 05C83 68W40 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi}, in: Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, January 6--8, 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 985--1003 (2013; Zbl 1423.05174) Full Text: DOI
Kawarabayashi, Ken-Ichi; Sommer, Christian; Thorup, Mikkel More compact oracles for approximate distances in undirected planar graphs. (English) Zbl 1423.68350 Khanna, Sanjeev (ed.), Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, January 6–8, 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 550-563 (2013). MSC: 68R10 05C10 05C12 05C85 68P05 68W05 PDFBibTeX XMLCite \textit{K.-I. Kawarabayashi} et al., in: Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, January 6--8, 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 550--563 (2013; Zbl 1423.68350) Full Text: DOI
Eickmeyer, Kord; Kawarabayashi, Ken-Ichi; Kreutzer, Stephan Model checking for successor-invariant first-order logic on minor-closed graph classes. (English) Zbl 1366.68168 Proceedings of the 2013 28th annual ACM/IEEE symposium on logic in computer science, LICS 2013, Tulane University, New Orleans, LA, USA, June 25–28, 2013. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-5020-6). 134-142 (2013). MSC: 68Q60 03B70 05C75 05C83 68Q25 PDFBibTeX XMLCite \textit{K. Eickmeyer} et al., in: Proceedings of the 2013 28th annual ACM/IEEE symposium on logic in computer science, LICS 2013, Tulane University, New Orleans, LA, USA, June 25--28, 2013. Los Alamitos, CA: IEEE Computer Society. 134--142 (2013; Zbl 1366.68168) Full Text: DOI
Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke An \(O(\log n)\)-approximation algorithm for the edge-disjoint paths problem in Eulerian planar graphs. (English) Zbl 1301.05333 ACM Trans. Algorithms 9, No. 2, Article No. 16, 13 p. (2013). MSC: 05C85 05C10 05C38 05C45 68W25 PDFBibTeX XMLCite \textit{K.-I. Kawarabayashi} and \textit{Y. Kobayashi}, ACM Trans. Algorithms 9, No. 2, Article No. 16, 13 p. (2013; Zbl 1301.05333) Full Text: DOI
Kawarabayashi, Ken-ichi; Kobayashi, Yusuke List-coloring graphs without subdivisions and without immersions. (English) Zbl 1425.05153 Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1425-1435 (2012). MSC: 05C85 05C15 68W25 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} and \textit{Y. Kobayashi}, in: Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17--19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1425--1435 (2012; Zbl 1425.05153) Full Text: Link
Kakimura, Naonori; Kawarabayashi, Ken-Ichi Packing directed circuits through prescribed vertices bounded fractionally. (English) Zbl 1256.05190 SIAM J. Discrete Math. 26, No. 3, 1121-1133 (2012). MSC: 05C70 05C20 05C60 05C38 05C85 68R10 68Q25 68W25 PDFBibTeX XMLCite \textit{N. Kakimura} and \textit{K.-I. Kawarabayashi}, SIAM J. Discrete Math. 26, No. 3, 1121--1133 (2012; Zbl 1256.05190) Full Text: DOI Link
Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke A linear time algorithm for the induced disjoint paths problem in planar graphs. (English) Zbl 1241.05058 J. Comput. Syst. Sci. 78, No. 2, 670-680 (2012). MSC: 05C38 05C10 05C85 PDFBibTeX XMLCite \textit{K.-I. Kawarabayashi} and \textit{Y. Kobayashi}, J. Comput. Syst. Sci. 78, No. 2, 670--680 (2012; Zbl 1241.05058) Full Text: DOI
Dvořák, Zdeněk; Kawarabayashi, Ken-Ichi; Thomas, Robin Three-coloring triangle-free planar graphs in linear time. (English) Zbl 1295.05231 ACM Trans. Algorithms 7, No. 4, Article No. 41, 14 p. (2011). MSC: 05C85 05C10 05C15 68Q25 PDFBibTeX XMLCite \textit{Z. Dvořák} et al., ACM Trans. Algorithms 7, No. 4, Article No. 41, 14 p. (2011; Zbl 1295.05231) Full Text: DOI arXiv
Kawarabayashi, Ken-ichi; Thorup, Mikkel The minimum \(k\)-way cut of bounded size is fixed-parameter tractable. (English) Zbl 1292.68094 Ostrovsky, Rafail (ed.), Proceedings of the 2011 IEEE 52nd annual symposium on foundations of computer science – FOCS 2011, Palm Springs, CA, USA, October 22–25. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-4571-4; 978-1-4577-1843-4/ebook). 160-169 (2011). MSC: 68Q15 05C85 68R10 05C10 05C40 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} and \textit{M. Thorup}, in: Proceedings of the 2011 IEEE 52nd annual symposium on foundations of computer science -- FOCS 2011, Palm Springs, CA, USA, October 22--25. Los Alamitos, CA: IEEE Computer Society. 160--169 (2011; Zbl 1292.68094) Full Text: DOI arXiv
Grohe, Martin; Kawarabayashi, Ken-ichi; Marx, Dániel; Wollan, Paul Finding topological subgraphs is fixed-parameter tractable. (English) Zbl 1288.05058 Proceedings of the 43rd annual ACM symposium on theory of computing, STOC ’11. San Jose, CA, USA, June 6–8, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0691-1). 479-488 (2011). MSC: 05C10 05C83 05C85 68Q25 PDFBibTeX XMLCite \textit{M. Grohe} et al., in: Proceedings of the 43rd annual ACM symposium on theory of computing, STOC '11. San Jose, CA, USA, June 6--8, 2011. New York, NY: Association for Computing Machinery (ACM). 479--488 (2011; Zbl 1288.05058) Full Text: DOI arXiv Link
Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Kawarabayashi, Ken-ichi Contraction decomposition in \(h\)-minor-free graphs and algorithmic applications. (English) Zbl 1288.05256 Proceedings of the 43rd annual ACM symposium on theory of computing, STOC ’11. San Jose, CA, USA, June 6–8, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0691-1). 441-450 (2011). MSC: 05C83 05C10 05C85 68Q25 68W25 68R10 PDFBibTeX XMLCite \textit{E. D. Demaine} et al., in: Proceedings of the 43rd annual ACM symposium on theory of computing, STOC '11. San Jose, CA, USA, June 6--8, 2011. New York, NY: Association for Computing Machinery (ACM). 441--450 (2011; Zbl 1288.05256) Full Text: DOI
Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke An improved algorithm for the half-disjoint paths problem. (English) Zbl 1237.05202 SIAM J. Discrete Math. 25, No. 3, 1322-1330 (2011). MSC: 05C85 05C38 05C83 05C05 05C12 PDFBibTeX XMLCite \textit{K.-I. Kawarabayashi} and \textit{Y. Kobayashi}, SIAM J. Discrete Math. 25, No. 3, 1322--1330 (2011; Zbl 1237.05202) Full Text: DOI
Kawarabayashi, Ken-ichi; Reed, Bruce An (almost) linear time algorithm for odd cycles transversal. (English) Zbl 1288.05280 Charikar, Moses (ed.), Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17–19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-0-89871-698-6/CD-ROM). 365-378 (2010). MSC: 05C85 05C35 05C10 05C38 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} and \textit{B. Reed}, in: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17--19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 365--378 (2010; Zbl 1288.05280)
Kawarabayashi, Ken-ichi; Kobayashi, Yusuke The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs. (English) Zbl 1288.05148 Charikar, Moses (ed.), Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17–19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-0-89871-698-6/CD-ROM). 345-353 (2010). MSC: 05C45 05C85 90C27 90C35 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} and \textit{Y. Kobayashi}, in: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17--19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 345--353 (2010; Zbl 1288.05148)
Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Kawarabayashi, Ken-ichi Decomposition, approximation, and coloring of odd-minor-free graphs. (English) Zbl 1288.05053 Charikar, Moses (ed.), Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17–19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-0-89871-698-6/CD-ROM). 329-344 (2010). MSC: 05C10 05C15 05C85 05C83 68R10 PDFBibTeX XMLCite \textit{E. D. Demaine} et al., in: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17--19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 329--344 (2010; Zbl 1288.05053)
Kawarabayashi, Ken-ichi; Li, Zhentao; Reed, Bruce Recognizing a totally odd \(K_{4}\)-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements. (English) Zbl 1288.05279 Charikar, Moses (ed.), Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17–19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-0-89871-698-6/CD-ROM). 318-328 (2010). MSC: 05C85 05C40 05C70 90C27 90C35 68Q17 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} et al., in: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17--19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 318--328 (2010; Zbl 1288.05279)
Kawarabayashi, Ken-ichi; Kobayashi, Yusuke An \(O(\log n)\)-approximation algorithm for the disjoint paths problem in Eulerian planar graphs and 4-edge-connected planar graphs. (English) Zbl 1305.68339 Serna, Maria (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 13th international workshop, APPROX 2010, and 14th international workshop, RANDOM 2010, Barcelona, Spain, September 1–3, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15368-6/pbk). Lecture Notes in Computer Science 6302, 274-286 (2010). MSC: 68W25 05C10 05C38 05C45 90C27 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} and \textit{Y. Kobayashi}, Lect. Notes Comput. Sci. 6302, 274--286 (2010; Zbl 1305.68339) Full Text: DOI
Kawarabayashi, Ken-Ichi; Ozeki, Kenta A simple algorithm for 4-coloring 3-colorable planar graphs. (English) Zbl 1209.05088 Theor. Comput. Sci. 411, No. 26-28, 2619-2622 (2010). MSC: 05C15 05C10 05C85 PDFBibTeX XMLCite \textit{K.-I. Kawarabayashi} and \textit{K. Ozeki}, Theor. Comput. Sci. 411, No. 26--28, 2619--2622 (2010; Zbl 1209.05088) Full Text: DOI
Dvořák, Zdeněk; Kawarabayashi, Ken-ichi; Thomas, Robin Three-coloring triangle-free planar graphs in linear time. (English) Zbl 1423.05064 Mathieu, Claire (ed.), Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, NY, USA, January 4–6, 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1176-1182 (2009). MSC: 05C15 05C10 05C85 68W40 PDFBibTeX XMLCite \textit{Z. Dvořák} et al., in: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, NY, USA, January 4--6, 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1176--1182 (2009; Zbl 1423.05064) Full Text: Link
Kawarabayashi, Ken-ichi; Demaine, Erik D.; Hajiaghayi, Mohammad Taghi Additive approximation algorithms for list-coloring minor-closed class of graphs. (English) Zbl 1423.05176 Mathieu, Claire (ed.), Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, NY, USA, January 4–6, 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1166-1175 (2009). MSC: 05C85 05C15 05C83 68W25 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} et al., in: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, NY, USA, January 4--6, 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1166--1175 (2009; Zbl 1423.05176) Full Text: Link
Kawarabayashi, Ken-ichi; Mohar, Bojan List-color-critical graphs on a fixed surface. (English) Zbl 1423.05070 Mathieu, Claire (ed.), Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, NY, USA, January 4–6, 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1156-1165 (2009). MSC: 05C15 05C10 05C85 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} and \textit{B. Mohar}, in: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, NY, USA, January 4--6, 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1156--1165 (2009; Zbl 1423.05070) Full Text: Link
Kobayashi, Yusuke; Kawarabayashi, Ken-ichi Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. (English) Zbl 1423.05179 Mathieu, Claire (ed.), Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, NY, USA, January 4–6, 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1146-1155 (2009). MSC: 05C85 05C10 05C38 68Q25 PDFBibTeX XMLCite \textit{Y. Kobayashi} and \textit{K.-i. Kawarabayashi}, in: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, NY, USA, January 4--6, 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1146--1155 (2009; Zbl 1423.05179) Full Text: Link
Kawarabayashi, Ken-ichi; Reed, Bruce Hadwiger’s conjecture is decidable. (English) Zbl 1304.05047 Proceedings of the 41st annual ACM symposium on theory of computing, STOC ’09. Bethesda, MD, USA, May 31 – June 2, 2009. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-613-7). 445-454 (2009). MSC: 05C15 05C75 05C85 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} and \textit{B. Reed}, in: Proceedings of the 41st annual ACM symposium on theory of computing, STOC '09. Bethesda, MD, USA, May 31 -- June 2, 2009. New York, NY: Association for Computing Machinery (ACM). 445--454 (2009; Zbl 1304.05047) Full Text: DOI
Kawarabayashi, Ken-ichi Planarity allowing few error vertices in linear time. (English) Zbl 1292.68093 2009 IEEE 50th annual symposium on foundations of computer science – FOCS 2009. Proceedings of the symposium, Atlanta, GA, USA, October 24–27, 2009. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-3850-1; 978-1-4244-5116-6/ebook). 639-648 (2009). MSC: 68Q25 68R10 05C10 05C85 68W25 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi}, in: 2009 IEEE 50th annual symposium on foundations of computer science -- FOCS 2009. Proceedings of the symposium, Atlanta, GA, USA, October 24--27, 2009. Los Alamitos, CA: IEEE Computer Society. 639--648 (2009; Zbl 1292.68093) Full Text: DOI
Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Kawarabayashi, Ken-ichi Algorithmic graph minor theory: Improved grid minor bounds and Wagner’s contraction. (English) Zbl 1184.05121 Algorithmica 54, No. 2, 142-180 (2009). MSC: 05C85 05C83 68R10 68Q25 PDFBibTeX XMLCite \textit{E. D. Demaine} et al., Algorithmica 54, No. 2, 142--180 (2009; Zbl 1184.05121) Full Text: DOI
Kawarabayashi, Ken-ichi Approximating list-coloring on a fixed surface. (English) Zbl 1153.05319 Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-70574-1/pbk). Lecture Notes in Computer Science 5125, 333-344 (2008). MSC: 05C15 05C10 05C85 68Q17 68Q25 68W25 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi}, Lect. Notes Comput. Sci. 5125, 333--344 (2008; Zbl 1153.05319) Full Text: DOI
Kawarabayashi, Ken-ichi; Mohar, Bojan Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs. (English) Zbl 1301.05334 Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 401-416 (2006). MSC: 05C85 05C15 05C83 68Q25 68W25 PDFBibTeX XMLCite \textit{K.-i. Kawarabayashi} and \textit{B. Mohar}, in: Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21--23, 2006. New York, NY: ACM Press. 401--416 (2006; Zbl 1301.05334) Full Text: DOI
Chudnovsky, Maria; Kawarabayashi, Ken-ichi; Seymour, Paul Detecting even holes. (English) Zbl 1062.05135 J. Graph Theory 48, No. 2, 85-111 (2005). Reviewer: Haiko Müller (Leeds) MSC: 05C85 05C22 PDFBibTeX XMLCite \textit{M. Chudnovsky} et al., J. Graph Theory 48, No. 2, 85--111 (2005; Zbl 1062.05135) Full Text: DOI