Linear and 2-Frugal Choosability of Graphs of Small Maximum Average DegreeReport as inadecuate




Linear and 2-Frugal Choosability of Graphs of Small Maximum Average Degree - Download this document for free, or read online. Document in PDF available to download.

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués

Abstract : A proper vertex colouring of a graph G is 2-frugal resp. linear if the graph induced by the vertices of any two colour classes is of maximum degree 2 resp. is a forest of paths. A graph G is 2-frugally resp. linearly L-colourable if for a given list assignment L : VG → N, there exists a 2-frugal resp. linear colouring c of G such that cv ∈ Lv for all v ∈ V G. If G is 2-frugally resp. linearly L-list colourable for any list assignment such that |Lv| ≥ k for all v ∈ V G, then G is 2-frugally resp. linearly k-choosable. In this paper, we improve some bounds on the 2-frugal choosability and linear choosability of graphs with small maximum average degree.





Author: Nathann Cohen - Frédéric Havet -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents