Cover Image

Characterization of cycle obstruction sets for improper coloring planar graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Choi, Ilkyoo, Liu, Chun-Hung, Oum, Sang-il
Format:	Preprint
Published:	2018
Subjects:	Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Between proper and square colorings of sparse graphs
by: Choi, Ilkyoo, et al.
Published: (2025)

The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs
by: Ahn, Jungho, et al.
Published: (2022)

Note on Hamiltonicity of basis graphs of even delta-matroids
by: Kim, Donggyu, et al.
Published: (2023)

Prime vertex-minors of a prime graph
by: Kim, Donggyu, et al.
Published: (2022)

Blind cop-width and balanced minors of graphs
by: Buffière, Hector, et al.
Published: (2025)

Linear bounds on treewidth in terms of excluded planar minors
by: Gollin, J. Pascal, et al.
Published: (2024)

Ramsey-type $χ$-bounds for $χ$-bounded graph classes
by: Nguyen, Tung, et al.
Published: (2026)

Obstructions for homomorphisms to odd cycles in series-parallel graphs
by: Cho, Eun-Kyung, et al.
Published: (2025)

Colouring t-perfect graphs
by: Chudnovsky, Maria, et al.
Published: (2024)

Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
by: Oum, Sang-il, et al.
Published: (2026)

Tight bound for independent domination of cubic graphs without $4$-cycles
by: Cho, Eun-Kyung, et al.
Published: (2021)

Twin-width of random graphs
by: Ahn, Jungho, et al.
Published: (2022)

Branch-width of represented matroids in matrix multiplication time
by: Choi, Mujin, et al.
Published: (2026)

Branch-width of connectivity functions is fixed-parameter tractable
by: Korhonen, Tuukka, et al.
Published: (2026)

Existence of cycles of length divisible by 3 or 4
by: Choi, Ilkyoo, et al.
Published: (2026)

Odd list-coloring of graphs of small Euler genus with no short cycles of specific types
by: Balaji, Rishi, et al.
Published: (2025)

Brooks-type theorems for relaxations of square colorings
by: Cho, Eun-Kyung, et al.
Published: (2023)

A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
by: Gollin, J. Pascal, et al.
Published: (2022)

Fragile minor-monotone parameters under random edge perturbation
by: Kang, Dong Yeap, et al.
Published: (2020)

Unavoidable pivot-minors in graphs of large rank-depth
by: Ahn, Jungho, et al.
Published: (2025)

Classification of real Bott manifolds and acyclic digraphs
by: Choi, Suyoung, et al.
Published: (2010)

Equitable coloring of graphs beyond planarity
by: Liu, Weichan
Published: (2025)

A lower bound on the number of edges in DP-critical graphs. II. Four colors
by: Bradshaw, Peter, et al.
Published: (2024)

On Alon-Tarsi orientations of sparse graphs
by: Cho, Eun-Kyung, et al.
Published: (2025)

A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
by: Gollin, J. Pascal, et al.
Published: (2021)

Flexible DP 3-coloring of sparse multigraphs
by: Bradshaw, Peter, et al.
Published: (2025)

Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k
by: Kanté, Mamadou Mostapha, et al.
Published: (2021)

Defective coloring is perfect for minors
by: Liu, Chun-Hung
Published: (2022)

Flexible DP-4-coloring of planar graphs without 4-cycles and intersecting triangles
by: Fang, Shu, et al.
Published: (2026)

Note on robust coloring of planar graphs
by: Kardoš, František, et al.
Published: (2024)

Extending total colorings in planar graphs
by: Henderschedt, Owen, et al.
Published: (2025)

Defective correspondence coloring of planar graphs
by: Anderson, James
Published: (2024)

Semistrong edge colorings of planar graphs
by: Lin, Yuquan, et al.
Published: (2024)

The interval coloring impropriety of planar graphs
by: Lee, Seunghun
Published: (2024)

Clustered Colouring of Odd-$H$-Minor-Free Graphs
by: Hickingbotham, Robert, et al.
Published: (2023)

Partition subcubic planar graphs into independent sets
by: Liu, Xujun, et al.
Published: (2024)

Twin-width of subdivisions of multigraphs
by: Ahn, Jungho, et al.
Published: (2023)

Reuniting $χ$-boundedness with polynomial $χ$-boundedness
by: Chudnovsky, Maria, et al.
Published: (2023)

The Erdős-Pósa property for circle graphs as vertex-minors
by: Campbell, Rutger, et al.
Published: (2025)

Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth
by: Liu, Chun-Hung
Published: (2022)