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

DOI10.1137/18M1177317MaRDI QIDQ5232160zbMATH OpenFDO

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)

Full work available at URL https://doi.org/10.1137/18M1177317

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)

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

Cites work

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

Cited in

(5)

• Extensions of fractional precolorings show discontinuous behavior
• 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

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)