Fractional Coloring Methods with Applications to Degenerate Graphs and Graphs on Surfaces

DOI10.1137/18M1177317zbMath1429.05068MaRDI QIDQ5232160

Carsten Thomassen, André Kündgen, John G. Gimbel, Bin Long Li

Publication date: 29 August 2019

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

zbMATH Keywords

fractional chromatic numberplanar graphsdegeneracygraphs on surfaces

Mathematics Subject Classification ID

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

Cites Work

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