Hard coloring problems in low degree planar bipartite graphs

Miroslav Chlebík, Janka Chlebı́ková

Type: Article

Publication Date: 2006-05-11

Citations: 17

DOI: https://doi.org/10.1016/j.dam.2006.03.014

View Publication

Locations

Discrete Applied Mathematics - View
Portsmouth Research Portal (University of Portsmouth) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Coloring Problems on Bipartite Graphs of Small Diameter	2020	Víctor Campos Guilherme C. M. Gomes Allen Ibiapina Raul Lopes Ignasi Sau Ana Silva
+ PDF Chat	Coloring Problems on Bipartite Graphs of Small Diameter	2021	Víctor Campos Guilherme C. M. Gomes Allen Ibiapina Raul Lopes Ignasi Sau Ana Silva
+	Graph Colouring with Input Restrictions	2013	Jian Song
+	Coloring Problems on Bipartite Graphs of Small Diameter	2020	Víctor Campos Guilherme C. M. Gomes Allen Ibiapina Raul Lopes Ignasi Sau Ana Silva
+	Subgraphs with restricted degrees of their vertices in planar graphs	1998	Igor Fabrici Stanislav Jendrol’
+ PDF Chat	Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs	2016	Konrad K. Dabrowski François Dross Matthew Johnson Daniël Paulusma
+	Solving Hard Computational Problems Efficiently: Asymptotic Parametric Complexity 3-Coloring Algorithm	2011	José Antonio Martín H.
+	Precoloring Extension. IV. General Bounds and List Colorings	2021	Mihály Hujter Zsolt Tuza
+ PDF Chat	Solving Hard Computational Problems Efficiently: Asymptotic Parametric Complexity 3-Coloring Algorithm	2013	José Antonio Martín H.
+	Solving Hard Computational Problems Efficiently: Asymptotic Parametric Complexity 3-Coloring Algorithm	2011	José Antonio Martín H.
+	Closing complexity gaps for coloring problems on H-free graphs	2014	Petr A. Golovach Daniël Paulusma Jian Song
+ PDF Chat	Open Problems on Graph Coloring for Special Graph Classes	2016	Daniël Paulusma
+ PDF Chat	Closing Complexity Gaps for Coloring Problems on H-Free Graphs	2012	Petr A. Golovach Daniël Paulusma Jian Song
+ PDF Chat	Relaxation of Wegner's Planar Graph Conjecture for Maximum Degree 4	2023	Eun‐Kyung Cho Ilkyoo Choi Bernard Lidický
+	Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8	2015	Zdeněk Dvořák Luke Postle
+	Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8	2015	Zdeněk Dvořák Luke Postle
+ PDF Chat	Relaxation of Wegner’s planar graph conjecture for maximum degree 4	2024	Eun‐Kyung Cho Ilkyoo Choi Bernard Lidický
+ PDF Chat	Graphs of maximum average degree less than $\frac {11}{3}$ are flexibly $4$-choosable	2024	Richard Bi Peter Bradshaw
+	A parametric-complexity exact 3-(UN)COLORING Algorithm	2011	José Antonio Martín H.
+	Linear coloring of planar graphs with large girth	2008	André Raspaud Weifan Wang

Works That Cite This (13)

Action	Title	Year	Authors
+	Solving Problems on Generalized Convex Graphs via Mim-Width	2020	Flavia Bonomo Nick Brettell Andrea Munaro Daniël Paulusma
+ PDF Chat	Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter	2022	Barnaby Martin Daniël Paulusma Siani Smith
+	Coloring graphs characterized by a forbidden subgraph	2014	Petr A. Golovach Daniël Paulusma Bernard Ries
+	A complexity dichotomy for critical values of the b-chromatic number of graphs	2020	Lars Jaffke Paloma T. Lima
+ PDF Chat	Filling the complexity gaps for colouring planar and bounded degree graphs	2019	Konrad K. Dabrowski François Dross Matthew Johnson Daniël Paulusma
+ PDF Chat	Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs	2016	Konrad K. Dabrowski François Dross Matthew Johnson Daniël Paulusma
+ PDF Chat	Open Problems on Graph Coloring for Special Graph Classes	2016	Daniël Paulusma
+	A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs	2018	Lars Jaffke Paloma T. Lima
+ PDF Chat	On List k-Coloring Convex Bipartite Graphs	2020	Josep Dı́az Öznur Yaşar Diner Marı́a Serna Oriol Serra
+	On List k-Coloring Convex Bipartite Graphs	2020	Josep Dı́az Öznur Yaşar Diner Marı́a Serna Oriol Serra

Works Cited by This (5)

Action	Title	Year	Authors
+	The optimum cost chromatic partition problem	1997	Klaus Jansen
+	PRECOLORING EXTENSION. II. GRAPHS CLASSES RELATED TO BIPARTITE GRAPHS	1993	Mihály Hujter Zs. Tuza
+ PDF Chat	Precoloring Extensions of Brooks' Theorem	2004	Michael O. Albertson Alexandr Kostochka Douglas B. West
+ PDF Chat	Precoloring extension. I. Interval graphs	1992	Miklós Bíró Mihály Hujter Zs. Tuza
+ PDF Chat	The colour theorems of Brooks and Gallai extended	1996	Alexandr Kostochka Michael Stiebitz Brunhilde Wirth