Vertex partitions of ($C 3 , C 4 , C 6$) -free planar graphs

François Dross; Pascal Ochem

doi:10.1016/j.disc.2019.07.002

Back

Vertex partitions of ($C 3 , C 4 , C 6$) -free planar graphs

Journal article

Open access

Peer reviewed

Vertex partitions of ($C 3 , C 4 , C 6$) -free planar graphs

François Dross and Pascal Ochem

Discrete Mathematics, Vol.342(11), pp.3229-3236

11/2019

DOI: https://doi.org/10.1016/j.disc.2019.07.002

Abstract

A graph is (k 1 , k 2)-colorable if its vertex set can be partitioned into a graph with maximum degree at most k 1 and and a graph with maximum degree at most k 2. We show that every (C 3 , C 4 , C 6)-free planar graph is (0, 6)-colorable. We also show that deciding whether a (C 3 , C 4 , C 6)-free planar graph is (0, 3)-colorable is NP-complete.

Files and links (2)

url

Find in HALView

url

https://doi.org/10.1016/j.disc.2019.07.002View

Published (Version of record) Open

Metrics

1 Record Views

Details

Title: Vertex partitions of ($C 3 , C 4 , C 6$) -free planar graphs
Creators - without role: François Dross - Laboratoire d'Informatique, Signaux et Systèmes de Sophia Antipolis
Pascal Ochem - Algorithmes, Graphes et Combinatoire
Publication Details: Discrete Mathematics, Vol.342(11), pp.3229-3236
Identifiers: 9947140709311
Academic Unit: Laboratoire d'Informatique de Robotique et de Microélectronique de Mtp - LIRMM
Language: English
Resource Type: Journal article
Local Fields: hal-02990467