Homomorphisms from sparse graphs with large girth.

DOI10.1016/S0095-8956(03)00081-9zbMath1033.05037OpenAlexW2024789683MaRDI QIDQ1425115

Alexandr V. Kostochka, Douglas B. West, Oleg V. Borodin, Seog-Jin Kim

Publication date: 15 March 2004

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0095-8956(03)00081-9

zbMATH Keywords

DischargingGraph coloringPlanar graphGraph homomorphism\(t\)-Nice graphsCircular coloringOriented coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (29)

On the odd girth and the circular chromatic number of generalized Petersen graphs ⋮ Homomorphisms and colourings of oriented graphs: an updated survey ⋮ The chromatic number of signed graphs with bounded maximum average degree ⋮ On the density of \(C_7\)-critical graphs ⋮ A Note on Circular Chromatic Number of Graphs with Large Girth and Similar Problems ⋮ Circular coloring of planar digraphs ⋮ Circular coloring and fractional coloring in planar graphs ⋮ Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$ ⋮ Fractional coloring planar graphs under Steinberg-type conditions ⋮ Pushable chromatic number of graphs with maximum average degree at most \(\frac{14}{5}\) ⋮ Homomorphisms to small negative even cycles ⋮ Density of 5/2-critical graphs ⋮ Nowhere-zero 3-flows and modulo \(k\)-orientations ⋮ An introduction to the discharging method via graph coloring ⋮ Counterexamples to Jaeger's circular flow conjecture ⋮ Circular consecutive choosability of k-choosable graphs ⋮ A Complexity Dichotomy for the Coloring of Sparse Graphs ⋮ A note onn-tuple colourings and circular colourings of planar graphs with large odd girth ⋮ Homomorphisms from sparse graphs to the Petersen graph ⋮ Circular vertex arboricity ⋮ Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k ⋮ Circular Flows in Planar Graphs ⋮ Approximability Distance in the Space of H-Colourability Problems ⋮ Circular choosability ⋮ Properties of an Approximability-related Parameter on Circular Complete Graphs ⋮ Complexity of planar signed graph homomorphisms to cycles ⋮ Homomorphisms of Signed Graphs ⋮ Homomorphisms of 2‐Edge‐Colored Triangle‐Free Planar Graphs ⋮ Complexity dichotomy for oriented homomorphism of planar graphs with large girth

Cites Work

• Unnamed Item
• Unnamed Item
• Homomorphisms of edge-colored graphs and Coxeter groups
• On the maximum average degree and the oriented chromatic number of a graph
• Colorings and girth of oriented planar graphs
• On universal graphs for planar oriented graphs of a given girth
• High-girth graphs avoiding a minor are nearly bipartite
• A note on the star chromatic number
• Star chromatic number
• (2 + ?)-Coloring of planar graphs with large odd-girth
• Circular chromatic number: A survey
• On nice graphs
• Circular chromatic number of planar graphs of large odd girth

This page was built for publication: Homomorphisms from sparse graphs with large girth.