Islands in Graphs on Surfaces

DOI10.1137/140957883zbMath1329.05105arXiv1402.2475OpenAlexW3103189813MaRDI QIDQ5743553

Pascal Ochem, Louis Esperet

Publication date: 5 February 2016

Published in: Discrete Mathematics, SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1402.2475

zbMATH Keywords

coloringgraphs on surfacescircular coloringmaximum average degreecircle graphsmonochromatic components

Mathematics Subject Classification ID

Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items (10)

Recoloring Planar Graphs of Girth at Least Five ⋮ Clustered 3-colouring graphs of bounded degree ⋮ Clustered variants of Hajós' conjecture ⋮ Partitioning sparse graphs into an independent set and a graph with bounded size components ⋮ On generalized choice and coloring numbers ⋮ Box representations of embedded graphs ⋮ Smaller universal targets for homomorphisms of edge-colored graphs ⋮ On the \(k\)-component independence number of a tree ⋮ Defective and clustered choosability of sparse graphs ⋮ Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On 1-improper 2-coloring of sparse graphs
• From the plane to higher surfaces
• Planar graphs are 1-relaxed, 4-choosable
• Every circle graph of girth at least 5 is 3-colourable
• Every planar graph is 5-choosable
• Covering and coloring polygon-circle graphs
• Bounded size components -- partitions and transversals.
• Partitioning into graphs with only small components
• Light subgraphs of order at most 3 in large maps of minimum degree 5 on compact 2-manifolds
• High-girth graphs avoiding a minor are nearly bipartite
• A not 3-choosable planar graph without 3-cycles
• Light subgraphs of graphs embedded in the plane. A survey
• Graph coloring with no large monochromatic components
• Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths
• On subgraphs without large components
• Colouring Planar Graphs With Three Colours and No Large Monochromatic Components

This page was built for publication: Islands in Graphs on Surfaces