Fractional coloring methods with applications to degenerate graphs and graphs on surfaces

DOI10.1137/18M1177317zbMATH Open1429.05068MaRDI QIDQ5232160FDOQ5232160

Authors: André Kündgen, Carsten Thomassen, John Gimbel, Binlong Li 

Publication date: 29 August 2019

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

Recommendations

• Girth and fractional chromatic number of planar graphs
• Planar graphs are \(9/2\)-colorable
• Colouring graphs on surfaces
• The fractional chromatic number of triangle-free graphs with \(\varDelta \leq 3\)
• Fractional coloring of planar graphs of girth five

zbMATH Keywords

degeneracyplanar graphsgraphs on surfacesfractional chromatic number

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Fractional graph theory, fuzzy graph theory (05C72)

Cites Work

• Title not available (Why is that?)
• Matching theory
• Graph Theory and Probability
• Graphs on surfaces
• Title not available (Why is that?)
• Maximum matching and a polyhedron with 0,1-vertices
• Kneser's conjecture, chromatic number, and homotopy
• The strong perfect graph theorem
• Embeddings of graphs with no short noncontractible cycles
• Color-critical graphs on a fixed surface
• The chromatic number of a graph of girth 5 on a fixed surface
• Grötzsch's theorem on 3-colorings
• Title not available (Why is that?)
• Coloring graphs with fixed genus and girth
• 4-chromatic projective graphs
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• Title not available (Why is that?)
• A (<5)-Colour Theorem for Planar Graphs
• The fractional chromatic number of mycielski's graphs
• Planar Ramsey numbers
• Graph minors. VII: Disjoint paths on a surface
• Decomposing a planar graph into an independent set and a 3-degenerate graph
• Coloring-flow duality of embedded graphs
• A new proof of Grünbaum's 3 color theorem
• A fractional analogue of Brooks' theorem
• Critical graphs with connected complements
• On Tutte's extension of the four-colour problem
• Girth and fractional chromatic number of planar graphs
• On critical subgraphs of colour-critical graphs
• Fractional coloring of triangle-free planar graphs
• Quadrangulations and 5-critical graphs on the projective plane

Cited In (5)

• Fractional chromatic number of uniform inflation graph, generalized circle and generalized wheel
• Coloring circle arrangements: new 4-chromatic planar graphs
• Coloring circle arrangements: new 4-chromatic planar graphs
• Fractional path coloring in bounded degree trees with applications
• Extensions of fractional precolorings show discontinuous behavior

This page was built for publication: Fractional coloring methods with applications to degenerate graphs and graphs on surfaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232160)