Frugal Colouring of Graphs

Omid Amini; Louis Esperet; Jan Van Den Heuvel

inria-00144318, version 2

Frugal Colouring of Graphs

Omid Amini ()^a^, 1, Louis Esperet ², Jan Van Den Heuvel ³

N° RR-6178 (2007)

Résumé : A $k$-frugal colouring of a graph~$G$ is a proper colouring of the vertices of~$G$ such that no colour appears more than~$k$ times in the neighbourhood of a vertex. This type of colouring was introduced by Hind, Molloy and Reed in 1997. In this paper, we study the frugal chromatic number of planar graphs, planar graphs with large girth, and outerplanar graphs, and relate this parameter with several well-studied colourings, such as colouring of the square, cyclic colouring, and $L(p,q)$-labelling. We also study frugal edge-colourings of multigraphs.

a – Polytechnique - X
1 : MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
2 : Laboratoire Bordelais de Recherche en Informatique (LaBRI)
CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) – Université Victor Segalen - Bordeaux II
3 : Department Mathematics [London] (LSE)
London School of Economics

inria-00144318, version 2
http://hal.inria.fr/inria-00144318
oai:hal.inria.fr:inria-00144318
Contributeur : Rapport De Recherche Inria <>
Soumis le : Jeudi 3 Mai 2007, 10:11:28
Dernière modification le : Mercredi 15 Octobre 2008, 14:53:26

Voir la fiche détaillée

Documents associés

PS :

PDF :

arXiv : 0705.0422

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Rapports</head>
<biblStruct type="report" xml:id="inria-00144318"><monogr>
<author><persName><forename>Omid</forename><surname>Amini</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis / Laboratoire I3S</orgName>
<orgName type="team">MASCOTTE</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Nice Sophia Antipolis [UNS]</orgName>
<orgName type="institution">CNRS : UMR7271</orgName>
</affiliation>
</author>
<author><persName><forename>Louis</forename><surname>Esperet</surname></persName>
<affiliation>
<orgName type="laboratory">LaBRI</orgName>
<orgName type="team">Laboratoire Bordelais de Recherche en Informatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5800</orgName>
<orgName type="institution">Université Sciences et Technologies - Bordeaux I</orgName>
<orgName type="institution">École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)</orgName>
<orgName type="institution">Université Victor Segalen - Bordeaux II</orgName>
</affiliation>
</author>
<author><persName><forename>Jan</forename><surname>Van Den Heuvel</surname></persName>
<affiliation>
<orgName type="laboratory">LSE</orgName>
<orgName type="team">Department Mathematics [London]</orgName>
<country>GB</country>
<orgName type="institution">London School of Economics</orgName>
</affiliation>
</author>
<title type="main" level="m">Frugal Colouring of Graphs</title><title type="main" level="m">Frugal Colouring of Graphs</title><imprint><biblScope type="publicationDate">2007-00-00</biblScope><biblScope type="pp">12</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00144318</idno><idno type="HALFile">http://hal.inria.fr/inria-00144318/PDF/RR-6178.pdf</idno></biblStruct>
</listBibl>
</listBibl>