Fractional total colourings of graphs of high girth

DOI10.1016/J.JCTB.2010.12.005zbMATH Open1234.05091DBLPjournals/jct/KaiserKK11arXiv0911.2808OpenAlexW2165425588WikidataQ57601394 ScholiaQ57601394MaRDI QIDQ651031FDOQ651031

Authors: Tomáš Kaiser, Daniel Král', Andrew D. King 

Publication date: 8 December 2011

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

Abstract: Reed conjectured that for every epsilon>0 and Delta there exists g such that the fractional total chromatic number of a graph with maximum degree Delta and girth at least g is at most Delta+1+epsilon. We prove the conjecture for Delta=3 and for even Delta>=4 in the following stronger form: For each of these values of Delta, there exists g such that the fractional total chromatic number of any graph with maximum degree Delta and girth at least g is equal to Delta+1.

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

Recommendations

• The last fraction of a fractional conjecture
• Total colourings of planar graphs with large girth
• The Total Chromatic Number of Graphs of High Minimum Degree
• Fractional total colouring
• The total chromatic number of graphs having large maximum degree

zbMATH Keywords

total colouringfractional total chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Maximum matching and a polyhedron with 0,1-vertices
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• An improved bound for the strong chromatic number
• Constructions for cubic graphs with large girth
• A bound on the total chromatic number
• Fractionally colouring total graphs
• The last fraction of a fractional conjecture
• On the Strong Chromatic Number
• Transversals of Vertex Partitions in Graphs
• The strong chromatic number of a graph
• A characterization of graphs with fractional total chromatic number equal to \(\Delta +2\)

Cited In (10)

• The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
• On the total coloring of generalized Petersen graphs
• Fractional colorings of cubic graphs with large girth
• Fractional DP-chromatic number of planar graphs of large girth
• Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
• On thef-matching polytope and the fractionalf-chromatic index
• Total and fractional total colourings of circulant graphs
• Girth and fractional chromatic number of planar graphs
• Generalized fractional total colorings of graphs
• The last fraction of a fractional conjecture

This page was built for publication: Fractional total colourings of graphs of high girth

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