Folding

We define folding of a directed graph as a coloring (or a homomorphism) which is injective on all the down sets of a given depth. While in general foldings are as complicated as homomorphisms for some some classes they present an useful tool to study colorings and homomorphisms. Our main result yields for any proper minor closed class C a folding (of any prescribed depth) using a fixed number of colors. This in turn yields (for any C) the existence of a Kk-free graph which bounds all Kk-free graphs belonging to C. This has been conjectured and solved for k=3. Particularly, we prove (without using 4CT) the existence of a graph H with chromatic number at most 5 and clique number at most 4, such that any planar graph G is homomorphic to H. This is sandwiched between 4CT and 5CT for planar graphs and the general case has bearing to Hadwiger Conjecture.

Data and Resources

Additional Info

Field Value
Source ISSN: 0095-8956
Author Nesetril, Jaroslav, Ossona de Mendez, Patrice
Maintainer CCSD
Last Updated May 11, 2026, 08:32 (UTC)
Created May 11, 2026, 08:32 (UTC)
Identifier hal-00081706
Language en
contributor Department of Applied Mathematics (KAM) (KAM) ; Univerzita Karlova [Praha, Česká republika] = Charles University [Prague, Czech Republic] = Université Charles [Prague, Republique tchèque] (UK)
creator Nesetril, Jaroslav
date 2006-05-11T00:00:00
harvest_object_id 46bb394c-5d26-48a9-88e7-a998df4ee442
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2026-03-12T00:00:00
relation info:eu-repo/semantics/altIdentifier/doi/10.1016/j.jctb.2006.02.002
set_spec type:ART